Linked lists in Go

A linked list is a structure with a finite set of elements where each element uses at least two memory locations: one for storing the data and the other for a pointer that links the current element to the next one in the sequence of elements that make the linked list. The biggest advantages of linked lists are that they are easy to understand and implement, and generic enough to be used in many different situations and model many different kinds of data.

The first element of a linked list is called the head, whereas the last element of a list is often called the tail. The first thing you should do when defining a linked list is to keep the head of the list in a separate variable because the head is the only thing that you need to access the entire linked list.

The following figure shows the graphical representation of a linked list and a doubly linked list. Doubly linked lists are more flexible, but require more housekeeping:

So, in this section, we will present a simple implementation of a linked list in Go saved in linkedList.go.

The code of linkedList.go will be presented in four parts.

The first part is as follows:

package main 
 
import ( 
   "fmt" 
) 

The second part contains the following Go code:

type Node struct { 
   Value int 
   Next  *Node 
} 
 
func addNode(t *Node, v int) int { 
   if root == nil { 
         t = &Node{v, nil} 
         root = t 
         return 0 
   } 
 
   if v == t.Value { 
         fmt.Println("Node already exists:", v) 
         return -1 
   } 
 
   if t.Next == nil { 
         t.Next = &Node{v, nil} 
         return -2 
   } 
 
   return addNode(t.Next, v)

 
} 

Here, you define the structure that will hold each element of the list and a function that allows you to add a new node to the list. In order to avoid duplicate entries, you should check whether a value already exists in the list or not. Note that addNode() is a recursive function because it calls itself and that this approach might be a little slower and require more memory than iterating.

The third part of the code is the traverse() function:

func traverse(t *Node) { 
   if t == nil { 
         fmt.Println("-> Empty list!") 
         return 
   } 
 
   for t != nil {

 
         fmt.Printf("%d -> ", t.Value) 
         t = t.Next 
   } 
   fmt.Println() 
} 

The for loop implements the iterative approach for visiting all the nodes in a linked list.

The last part is as follows:

var root = new(Node)
func main() { 
   fmt.Println(root) 
   root = nil 
   traverse(root) 
   addNode(root, 1) 
   addNode(root, 1) 
   traverse(root) 
   addNode(root, 10) 
   addNode(root, 5) 
   addNode(root, 0) 
   addNode(root, 0) 
   traverse(root) 
   addNode(root, 100) 
   traverse(root) 
}

For the first time in this book, you see the use of a global variable that is not a constant. Global variables can be accessed and changed from anywhere in a program, which makes their use both practical and dangerous for that reason. The reason for using a global variable, which is named root, to hold the root of the linked list is to show whether the linked list is empty or not. This happens because integer values in Go are initialized as 0; so new(Node) is in fact {0 <nil>}, which makes it impossible to tell whether the head of the list is nil or not without passing an extra variable to each function that manipulates the linked list.

Executing linkedList.go will generate the following output:

$ go run linkedList.go
&{0 <nil>}
-> Empty list!
Node already exists: 1
1 ->
Node already exists: 0
1 -> 10 -> 5 -> 0 ->
1 -> 10 -> 5 -> 0 -> 100 ->