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.
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
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)
}
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:
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:
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:
Feel free to contact me if you have any questions or suggestions.
The above is the detailed content of Singly Linked List Implementation in Go. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
