Singly-linked list in Go

Components of a singly linked list

In a singly linked list, a node is a fundamental element that constitutes the structure of the list. A singly linked list is a linear data structure where each element is stored in a node, and each node contains two main components:

Data: The data component of a node holds the value or information associated with that particular node. This value can be of any data type, such as integers, strings, or complex objects.
Next pointer: The next pointer, also known as a reference or link, points to the next node in the sequence. It establishes the connection between nodes in the list, creating a unidirectional flow from one node to the next. In a singly linked list, the next pointer of the last node typically points to nil, indicating the end of the list.

The head pointer within the linked list marks an initial node. To traverse the linked list, we initiate the process at the head pointer and end upon reaching a null value.

Code

Here's an example of how you can implement a singly linked list in Go:

package main
import (
	"fmt"
)
// Define the Node structure
type Node struct {
	data int
	next *Node
}
// Define the LinkedList structure
type LinkedList struct {
	head *Node
}
// Initialize a new empty linked list
func NewLinkedList() *LinkedList {
	return &LinkedList{}
}
// Add a new node at the end of the linked list
func (ll *LinkedList) Append(data int) {
	newNode := &Node{data: data, next: nil}
	if ll.head == nil {
		ll.head = newNode
		return
	}
	current := ll.head
	for current.next != nil {
		current = current.next
	}
	current.next = newNode
}
// Display the linked list
func (ll *LinkedList) Display() {
	current := ll.head
	for current != nil {
		fmt.Printf("%d -> ", current.data)
		current = current.next
	}
	fmt.Println("nil")
}
func main() {
	// Create a new linked list
	ll := NewLinkedList()
	// Add elements to the linked list
	ll.Append(10)
	ll.Append(20)
	ll.Append(30)
	// Display the linked list
	fmt.Println("Linked List:")
	ll.Display()
}

This code defines a simple singly linked list in Go. It includes the following features:

Lines 8–11: The Node struct represents each node in the linked list. Each node contains an integer value (data) and a pointer to the next node (next).
Lines 14–16: The LinkedList struct represents the linked list itself and contains a pointer to the head node (head).
Lines 19–21: The NewLinkedList function initializes a new empty linked list.
Lines 24–37: The Append method adds a new node with the given data to the end of the linked list.
- Lines 25–35: Creates a new node with the given data and then traverses the list from the head node to the last node.
- Line 36: Once it reaches the last node, it updates the next pointer of the last node to point to the newly created node, effectively linking it at the end of the list.
Lines 40–47: The Display method prints the elements of the linked list.
- Lines 41–45: The function iterates through the linked list starting from the head node. It prints each node's data while traversing, followed by an arrow pointing to the next node.
- Line 46: Ends with nil to indicate the list's termination.

In the main function, we create a new linked list, add elements to it, and then display the linked list. You can customize and extend this basic implementation to include more functionalities, such as inserting nodes at specific positions, deleting nodes, and more.

Time and space complexity

A singly linked list offers efficient time complexity of $O(1)$ for insertion and deletion at the beginning of the list. However, its time complexity for insertion and deletion at the end is $O(n)$ due to the need to traverse the list. Space complexity is $O(n)$ as each node requires memory for data storage and the next pointer.

Free Resources