Linked lists are one of the most common data structures used for dynamic memory allocation. Here, a list of a finite set of elements is created, which contains at least two memory locations: one for the data element and another for the pointer that links the next set of elements. This Go programming tutorial explains how different linked lists can be implemented using pointers and structure types in go.
Data Structures in Go
the random access memory (RAM) can be visualized as a table, matrix, or a grid of addressable locations. In order to store values in the table, Go programmers need to designate it into locatable structures. These locatable structures are given a convenient name called variable name. Understand that a name given to a variable is only for the convenience of the programmer; Once the program is compiled, the variable name is replaced with a reference (or memory address, such as 0x78BAC). In the simplest form, a variable name can refer to a single cell. But in complicated situations, it can be a contiguous memory location or a matrix with a row and column called an array. An array can be programmatically accessed by its index, such as array_name[2][4]which may mean elements in the 2nd column and 4th row.
However, in another complicated situation, the structural relationship between the data elements may not be stored in a contiguous fashion; rather they may be stored randomly, such as in a tree structure representing hierarchical relationships, branching relationships, or a complex multilink structure with many interconnections.
Therefore, in order to store structural relationships present within data, Go developers need to define the memory layout and access strategies according to their specific need.
Before you continue, you may want to read: How to Use Structures in Go.
Static and dynamic memory allocation in Go
An important fact about memory allocation are the properties called dynamic and static nature. The size and location of a static data structure is predefined, while in a dynamic data structure, the size and location is undefined or decided at runtime.
For example, as Go developers define an array, they provide a static value of its size so the compiler knows exactly what location they are referring to when they provide index values. In dynamic data structures, such as linked lists, the next data element location is decided only when it is created during the execution phase. The size of the dynamic data structure can grow or shrink at runtime. Since static data structures are stored in contiguous memory locations, they work in a linear fashion, where data elements are stored in sequence.
The basis of dynamic data structures is called a linked list. Here, data elements are stored in a random location in the memory with a link to access each of the elements. Therefore a linked list contains at least two elements: one that represents a data element and another a link to the next structure.
Reading: How to Use Pointers in Go
Comparing Sequential and Linked Allocation in Go
Unlike sequential structures, such as arrays, linked allocation needs additional memory to store not only the data element, but also an element to store a link to the next element. This can be a dominant factor in some situations, but the efficiency gained through linked allocation far outweighs its disadvantages. For example, the memory allocated size is fixed in arrays, therefore, a lot of it can remain unused. While in linked allocation the question of unused allocation does not arise because here a node is created only when it is needed.
It is easy to delete items in a linked list but in sequential allocation deletion typically implies moving a large part of the data elements to different locations. Also, the insertion of data is quick in linked allocation. However, referring to a random part of the list is much faster in cases of sequential allocation.
Each method of storage has its pros and cons. Choosing the right structure is at the discretion of the Go programmer.
Types of linked lists
There are three basic ways a linked list can represent memory: linear, circular, doubly, and doubly-circular.
In a linear or singly linked list there is a single link element that points to the next node in the list. The next element of the last linking node points to nil, so as the list is traversed from start to end, the list is represented as soon as nil is encountered.
The circular linked list is the same as a linear list except that the last node points to the first node. Traversing can occur until the next element contains the address of the first node. Since the last node points to the first, circular traversal is possible.
In a doubly linked list, two linked addresses are provided: one that links to the previous node and another to the next node. Unlike linear lists, this is clearly an advantage, because the traversing can occur in both directions. Finding data elements can be quick.
A doubly-circular linked list is the same as a doubly-linked list except that the next element of the last node links back to the first node and the previous element links to the last node. This makes circular traversal possible in both directions.
Note that the flexibility increases as we move from singly to doubly linked list and circular to doubly-circular.
Let us implement each of these types of Go linked lists with some of the examples below. To keep things simple, we will restrict mostly to creation and traversal of the list only.
Reading: Revisiting Arrays and Slices in Go
Singly Linked List Example in Go
Below is an example of how to create a singly linked list in Go:
package main import ( “fmt” “math/rand” ) type Node struct { info interface{} next *Node } type List struct { head *Node } func (l *List) Insert(d interface{}) { list := &Node{info: d, next: nil} if l.head == nil { l.head = list } else { p := l.head for p.next != nil { p = p.next } p.next = list } } func Show(l *List) { p := l.head for p != nil { fmt.Printf(“-> %v “, p.info) p = p.next } } func main() { sl := List{} for i := 0; i < 5; i++ { sl.Insert(rand.Intn(100)) } Show(&sl) }
The expected output of running this Golang code in your integrated development environment is:
-> 81 -> 87 -> 47 -> 59 -> 81
Circular linked list code example in Go
We can easily convert a single linked list into circular. So, without changing the above code, add these two functions: ConvertSinglyToCircular and ShowCircular. Invoke these two functions from the main, that is all.
Here are the two functions:
func ShowCircular(l *List) { p := l.head for { if p.next == l.head { fmt.Printf(“-> %v “, p.info) break } fmt.Printf(“-> %v “, p.info) p = p.next } } func ConvertSinglyToCircular(l *List) { p := l.head for p.next != nil { p = p.next } p.next = l.head }
Now, invoke the functions from main as follows:
func main() { sl := List{} for i := 0; i < 5; i++ { sl.Insert(rand.Intn(100)) } ConvertSinglyToCircular(&sl) fmt.Println() ShowCircular(&sl) }
Reading: Understanding Garbage Collection in Go
Doubly linked list code example in Go
Here is a code example showing how to create doubly linked lists in Golang:
package main import ( “fmt” “math/rand” “time” ) type Node struct { info interface{} prev *Node next *Node } type List struct { head *Node tail *Node } func (l *List) Insert( d interface{}) { list := &Node{info: d, prev: nil, next: nil} if l.head == nil { l.head = list l.tail = list } else { p := l.head for p.next != nil { p = p.next } list.prev = p p.next = list l.tail = list } } func Show(l *List) { p := l.head for p != nil { fmt.Printf(“-> %v “, p.info) p = p.next } } func ReverseShow(l *List) { r := l.tail for r != nil { fmt.Printf(“-> %v “, r.info) r = r.prev } } func main() { sl := List{} seed := rand.NewSource(time.Now().UnixNano()) rnd := rand.New( seed) for i := 0; i < 10; i++ { sl.Insert(rnd.Intn(100)) } Show(&sl) fmt.Println("n-------------------------------------- ---") ReverseShow(&sl) }
The expected output of running this Go code example in your code editor would be:
-> 11 -> 17 -> 56 -> 71 -> 39 -> 44 -> 18 -> 78 -> 25 -> 19 ——————– ——– -> 19 -> 25 -> 78 -> 18 -> 44 -> 39 -> 71 -> 56 -> 17 -> 11
Doubly Circular Linked List Example in Go
Much like the circular linked list, a doubly circular linked list can easily be converted from the doubly linked list. We will just add two functions to the code above. The rest of the code remains the same, except for a slight modification in the main function, as we have seen in the case of our circular linked list example:
func ConvertDoublyToDoublyCircular(l *List) { l.head.prev = l.tail l.tail.next = l.head } func ShowDoublyCircular(l *List) { p := l.head for { if p.next == l .head { fmt.Printf(“-> %v “, p.info) break } fmt.Printf(“-> %v “, p.info) p = p.next } } func ReverseShowDoublyCircular(l *List) { r := l.tail for { if r.prev == l.tail { fmt.Printf(“-> %v “, r.info) break } fmt.Printf(“-> %v “, r.info) r = r.prev } } func main() { sl := List{} seed := rand.NewSource(time.Now().UnixNano()) rnd := rand.New(seed) for i := 0; i < 10; i++ { sl.Insert(rnd.Intn(100)) } ConvertDoublyToDoublyCircular(&sl) ShowDoublyCircular(&sl) fmt.Println("n--------------------- -------") ReverseShowDoublyCircular(&sl) }
Final Thoughts on Programming Go Linked Lists
As we can see, a linked list is quite easy to implement in Go and Golang. Linked allocations are used to model different types of data, be it single values or complex data structures with many fields. Access is really fast in sequential searching when used with pointers. There are several optimization techniques associated with linked lists. Doubly linked lists have higher efficacy than the singular linked allocation. The traversal can be quick in both directions. This is clearly a significant advantage.
