Go での単一リンクリストの実装

Hey there DEV.to community!

This is a part of my data structures and algorithms series. In this article, we will implement a singly linked list then in the next articles from this series I will implement other kinds of linked lists as well using Go.

Image source: GeeksforGeeks

To implement a singly linked list we need to structures, a node and a singly linked list itself. But before beginning to code here is how I like to organize my code:

project
├── singly_linked_list
│   ├── node.go
│   └── list.go
└── main.go

Node

A node only holds data and a pointer to the next node in its simplest form. Thus here is the struct we are going to use as a node (in the node.go file):

type SinglyNode struct {
    data interface{}
    next *SinglyNode
}

We are using interface{} as the data type for data in the struct so we may store any data we want inside the node.

Then we should define some methods to utilize the node struct we've just created.

func NewSinglyNode(data interface{}) *SinglyNode {
    return &SinglyNode{data: data}
}

If you are used to object-oriented languages you are mostly likely to be familiar with what a constructor is. Since Go is not an object-oriented language there are no classes but by some conventions around the Go world, we usually create a function prefixed with the word New. But keep in mind that in the OOP languages new is a special keyword that means creating an object. Here the New is just a name prefix and nothing more.

The NewSinglyNode function receives only one argument called data with interface{} type and returns a pointer of SinglyNode.

Next, we define some getters and setters for the node:

func (n *SinglyNode) SetData(data interface{}) {
    n.data = data
}

func (n *SinglyNode) SetNext(next *SinglyNode) {
    n.next = next
}

func (n *SinglyNode) GetData() interface{} {
    return n.data
}

func (n *SinglyNode) GetNext() (*SinglyNode, error) {
    if n.next == nil {
        return nil, errors.New("no next node")
    }
    return n.next, nil
}

The SetData, Setnext and GetData are pretty much self-explanatory. The GetNext returns two values, a pointer to the next SinglyNode and an error if there is no next node.

Here is an extra function I always like to add so I can always know how the string representation of my struct is:

func (n *SinglyNode) ToString() string {
    return n.data.(string)
}

List

Now that we are done with our node we should implement the list itself. A singly linked list holds the first node as head and as for my own preference two more data called last holds the last node and a country property that holds the count of the nodes added to the list.

So here is the first lines of the list.go file:

type SinglyLinkedList struct {
    head  *SinglyNode
    last  *SinglyNode
    count int
}

And obviously, a constructor-like function to create a SinglyLinkedList with ease:

func NewSinglyLinkedList() *SinglyLinkedList {
    return &SinglyLinkedList{}
}

The most important function in a linked list is the one that adds a node. Here is my implementation of such a function:

func (l *SinglyLinkedList) AttachNode(node *SinglyNode) {
    if l.head == nil {
        l.head = node
    } else {
        l.last.SetNext(node)
    }
    l.last = node
    l.count++
}

The function does as below:

• Check if the head of the linked list is empty, if so set the received node as the head of the list.
• If the head is not empty it sets the received node as the next property of the last node.
• Regardless of what happened before, the current node should be last node so the next time a node gets added it can get set as the next for the last node in our list.
• Increase the count by one.

Here is a function that receives data and creates a node and passes it to the AttachNode function:

func (l *SinglyLinkedList) Add(data interface{}) {
    l.AttachNode(NewSinglyNode(data))
}

Although this function might seem redundant, it will ease adding nodes to the list without manually creating one each time.

A function to get the count property as well:

func (l *SinglyLinkedList) Count() int {
    return l.count
}

The last function needed is a function that should return the next node in the linked list:

func (l *SinglyLinkedList) GetNext() (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    return l.head, nil
}

I prefer to name this function as same as the GetNext function defined for the nodes. This is done so there is more consistency. When first accessing a linked list the type is a linked list so there is no access to functions defined for nodes. Defining a function with the same name will make you able to use GetNext as much as you want to traverse your list.

One extra function that I always tend to add is a function to retrieve a node by the index:

func (l *SinglyLinkedList) GetByIndex(index int) (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    if index+1 > l.count {
        return nil, errors.New("index out of range")
    }
    node, _ := l.GetNext()
    for i := 0; i < index; i++ {
        node, _ = node.GetNext()
    }
    return node, nil
}

This function does as below:

• Check if the head is empty to return an error
• Check if index+1 is greater than the count of the list to return an error. We check for index+1 and not for index since we consider the indices starting from 0 just like arrays.
• Assign l.GetNext() to a variable named node (ignoring the error with _) then loop for one less than the index provided as we already have the first one stored in the node variable, assigning the next node of the current node as node again.
• Return the traversed node without an error.

Testing

Now that we have our linked list and node definitions, we can test it in our main.go file just as below:

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    firstNode, err := list.GetNext()
    if err != nil {
        panic(err)
    }

    secondNode, err := firstNode.GetNext()
    if err != nil {
        panic(err)
    }

    thirdNode, err := secondNode.GetNext()
    if err != nil {
        panic(err)
    }

    println(firstNode.ToString())  // One
    println(secondNode.ToString()) // Two
    println(thirdNode.ToString())  // Three
}

Or using the GetByIndex function:

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    node, err := list.GetByIndex(2)
    if err != nil {
        panic(err)
    }

    fmt.Println(node.ToString()) // Three
}

---

BTW! Check out my free Node.js Essentials E-book here:

NodeJS Essentials | Free E-Book

Adnan Babakan (he/him) ・ Sep 11 '20

#node #javascript #books

Feel free to contact me if you have any questions or suggestions.

以上がGo での単一リンクリストの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。