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.

graph LR;
    A[Node 1: Value] --> B[Node 2: Value]
    B --> C[Node 3: Value]
    C --> D[Null]

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

graph LR;
    A[Node 1] -->|next| B[Node 2]
    B -->|next| C[Node 3]
    C -->|prev| B
    B -->|prev| A

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

graph LR;
    A[Node 1] -->|next| B[Node 2]
    B -->|next| C[Node 3]
    C -->|next| A

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 the linked list.
type Node struct {
  data interface{}
  next *Node
}

// LinkedList represents a singly linked list.
type LinkedList struct {
  head *Node
}

// NewLinkedList creates a new empty linked list.
func NewLinkedList() *LinkedList {
  return &LinkedList{}
}

// Append adds a new node with the given data to the end of the linked list.
func (l *LinkedList) Append(data interface{}) {
  newNode := &Node{data: data, next: nil}
  if l.head == nil {
    l.head = newNode
    return
  }
  current := l.head
  for current.next != nil {
    current = current.next
  }
  current.next = newNode
}

// Display prints the elements of the linked list.
func (l *LinkedList) Display() {
  current := l.head
  for current != nil {
    fmt.Print(current.data, " -> ")
    current = current.next
  }
  fmt.Println("nil")
}

Strings Stacks