linked list illustration

A list is an ordered collection of elements.

When data is stored in a linked list , data is stored in a sequence of nodes .

A linked list , as an Abstract Data Type, is often compared to arrays , but instead of putting values in ‘boxes’, (for lack of a better word), the data is stored in the form of nodes , that are linked together.  Each node of the linked list, except for the last one, contains a memory address indicating the location of the next node .

So, a singly linked list in Go is a structure with a finite set of elements where each element uses 2 memory locations:
-one for storing the data , -and the other for a pointer to the next element.

The advantage of a linked list resides in the fact that they are easy to apprehend and generic enough to be used in many different scenarios.

Another variant of this ADT is the doubly linked list where the difference resides in the fact that each node contains the memory address of the previous node (except for the first one) and the memory address of the next node.
 

We will code a singly linked list using Go Generics, let’s call this program   ’linkedlist.go’ :
 


package main

import (
	"fmt"
)

// Node represents a node in the linked list
type Node[T any] struct {
	data T
	next *Node[T]
}

// LinkedList represents a linked list
type LinkedList[T any] struct {
	head   *Node[T]
	length int
}

// Append method adds a new node with the given data at the end of the list.
// Appends takes a parameter 'data' of generic type 'T' . 
// 'll' is the receiver of this method representing the instance of 'LinkedList' on which 'Append' is called.
func (ll *LinkedList[T]) Append(data T) {
	// A new node is created and a pointer is assigned to 'newNode'.
	// This new node will be appended to the end of the list.
	// The node is of type 'Node[T]' with 'data' set to the value passed to the 'Append' method.
	newNode := &Node[T]{data: data}
	// The 'if' statement checks if the list is empty (i.e, 'head' is nil).
	// If the list is empty, the new node will become the first(head) of the list.
	if ll.head == nil {
		// In case of empty list (i.e,'head' is 'nil'), the head of the list set tot the new node.
		ll.head = newNode
		// The 'else' block is executed if the list already has one node (i.e, 'head' is not 'nil').
	} else {
		// A local variable 'current' is assigned to the value of 'head' marking the start of the list.
		// This variable will be used to traverse the entire list.
		current := ll.head
		// A loop iterates through the list and continues until 'current.next' is 'nil', indicating that 'current' is the last node in the list.
		for current.next != nil {
			// Within this loop, 'current' is updates to point to the next node in the list, moving the traversal process forward.
			current = current.next
		}
		// Once the end of list is reached(the last node where 'current.next' is 'nil'), this line 
		// sets 'current.next' to the new node, effectively appending the new node to the end of the list.
		current.next = newNode
	}
	// Incrementing the 'length' field of the 'LinkedList', thus keeping track of the number of nodes in the list.
	ll.length++
}

// Prepend method adds a new node with the given data at the beginning of the list
func (ll *LinkedList[T]) Prepend(data T) {
	newNode := &Node[T]{data: data, next: ll.head}
	ll.head = newNode
	ll.length++
}

// PrintListData method prints the data of each node in the list .
func (ll *LinkedList[T]) PrintListData() {
	current := ll.head
	for current != nil {
		fmt.Printf("%v ", current.data)
		current = current.next
	}
	fmt.Println()
}

// String method returns a string representation of the list . 
func (ll *LinkedList[T]) String() string {
	return fmt.Sprint(ll.length)
}

func main() {
	// Nodes containing integer values
	integerList := LinkedList[int]{}
	integerList.Prepend(2)
	integerList.Prepend(1)
	integerList.Append(3)

	fmt.Printf("There are %s nodes containing the following values: ", integerList.String())
	integerList.PrintListData()

	// Nodes containing string values
	stringList := LinkedList[string]{}
	stringList.Append("'Hello'")
	stringList.Append("'World'")
	stringList.Append("'!'")

	fmt.Printf("There are %s nodes containing the following values: ", stringList.String())
	stringList.PrintListData()
}

The terminal should print out :

There are 3 nodes containing the following values: 1 2 3 
There are 3 nodes containing the following values: 'Hello' 'World' '!' 

 

  Important Consideration !

Gaining proficiency in pointers can be effectively achieved through the utilization of linked lists in Go.

-Fundamentals of Pointers -> The essence of linked lists lies in the use of pointers for interconnecting nodes.

-Management of Memory -> The construction of a linked list in Go necessitates meticulous control over memory, along with a comprehensive understanding of how the language handles memory allocation for structs and pointers.

-Operations on Pointers -> Engaging with linked lists means performing specific pointer-related operations, including dereferencing and using the ‘&’ operator to obtain a variable’s address.