Linked Lists

learnings

Programming

Linked Lists

Linked lists are a fundamental data structure that provide an alternative to arrays in storing sequences of elements. They are particularly useful in scenarios where the size of the data is unknown ahead of time or when frequent insertions and deletions are required.

Overview of Linked Lists

Structure: A linked list is a collection of nodes, where each node contains data and a reference (or pointer) to the next node in the sequence. The first node is called the head, and the last node points to null (or nil), indicating the end of the list.

Types of Linked Lists:

Singly Linked List: Each node has only one pointer to the next node.

Doubly Linked List: Each node has two pointers, one to the next node and one to the previous node.

Circular Linked List: The last node points back to the first node, forming a circle.

Dynamic Size: Unlike arrays, linked lists do not have a fixed size and can grow or shrink dynamically.
Memory Allocation: Each element (node) in a linked list is independently allocated in memory, not necessarily in contiguous memory locations like arrays.
Access: Linked lists allow sequential access to elements, not direct access. This means you have to traverse the list from the beginning to access a particular element.

Common Operations and Their Big O Notation

Operation	Time Complexity	Comments
Access	O(n)	Accessing an element requires traversing the list from the head to the desired position.
Search	O(n)	Searching for an element requires traversing the list to find the element.
Insertion	O(1) (average)	Inserting at the head or tail (if tail is known) is O(1). Inserting at a specific position requires O(n) to find the position, but the insertion itself is O(1).
Deletion	O(1) (average)	Deleting the head is O(1). Deleting at a specific position requires O(n) to find the node, but the deletion itself is O(1).
Traversal	O(n)	Traversing the entire list requires O(n) time as each element must be visited.

Advantages of Linked Lists

Dynamic Size: Can grow or shrink in size, unlike static arrays.
Efficient Insertions/Deletions: Particularly at the beginning or end of the list (if tail is maintained), as no shifting of elements is required.

Disadvantages of Linked Lists

Memory Overhead: Each node requires extra memory for storing the pointer(s).
No Random Access: Direct access to elements by index is not possible; elements must be accessed sequentially.
Cache Performance: Not as cache-friendly as arrays due to non-contiguous memory allocation.

Applications

Suitable for applications with unpredictable memory requirements.
Often used as the underlying structure for implementing other data structures like stacks, queues, and adjacency lists in graph representations.

Understanding linked lists and their operations is crucial for many algorithm problems and data structure implementations. They are particularly favored in problems where the dynamic allocation and efficient insertion/deletion capabilities of linked lists can be leveraged.

Code representation

linked_list.go

// Node represents a node in a simple linked list
type Node struct {
	Value int
	Next  *Node
}

// LinkedList represents a simple linked list
type LinkedList struct {
	Head *Node
}

// Append adds a new node with the given value to the end of the list
func (l *LinkedList) Append(value int) {
	newNode := &Node{Value: value}

	if l.Head == nil {
		l.Head = newNode
		return
	}

	current := l.Head
	for current.Next != nil {
		current = current.Next
	}

	current.Next = newNode
}

// Print displays the linked list with -> arrows between nodes
func (l *LinkedList) Print() {
	if l.Head == nil {
		fmt.Println("Empty list")
		return
	}

	current := l.Head
	for current != nil {
		fmt.Printf("%d", current.Value)
		if current.Next != nil {
			fmt.Print(" -> ")
		}
		current = current.Next
	}
	fmt.Println()
}

Doubly-linked list

boubly_linked_list.go

// DNode represents a node in a doubly linked list
type DNode struct {
	Value int
	Next  *DNode
	Prev  *DNode
}

// DoublyLinkedList represents a doubly linked list
type DoublyLinkedList struct {
	Head *DNode
	Tail *DNode
}

// Append adds a new node with the given value to the end of the list
func (d *DoublyLinkedList) Append(value int) {
	newNode := &DNode{Value: value}

	if d.Head == nil {
		d.Head = newNode
		d.Tail = newNode
		return
	}

	newNode.Prev = d.Tail
	d.Tail.Next = newNode
	d.Tail = newNode
}

// Print displays the doubly linked list with -> arrows for forward connections
// and <- for backward connections
func (d *DoublyLinkedList) Print() {
	if d.Head == nil {
		fmt.Println("Empty list")
		return
	}

	// Forward traversal
	fmt.Print("Forward: ")
	current := d.Head
	for current != nil {
		fmt.Printf("%d", current.Value)
		if current.Next != nil {
			fmt.Print(" -> ")
		}
		current = current.Next
	}
	fmt.Println()

	// Backward traversal
	fmt.Print("Backward: ")
	current = d.Tail
	for current != nil {
		fmt.Printf("%d", current.Value)
		if current.Prev != nil {
			fmt.Print(" <- ")
		}
		current = current.Prev
	}
	fmt.Println()
}

main.go

func main() {
	// Example of simple linked list
	fmt.Println("Simple Linked List Example:")
	list := LinkedList{}
	list.Append(1)
	list.Append(2)
	list.Append(3)
	list.Append(4)
	list.Print()
	// Output: 1 -> 2 -> 3 -> 4

	// Example of doubly linked list
	fmt.Println("\nDoubly Linked List Example:")
	dlist := DoublyLinkedList{}
	dlist.Append(10)
	dlist.Append(20)
	dlist.Append(30)
	dlist.Append(40)
	dlist.Print()

	// Output:
	// Forward: 10 -> 20 -> 30 -> 40
	// Backward: 40 <- 30 <- 20 <- 10
}

Strings Stacks