Linked List Fundamentals

A linked list is a fundamental data structure that represents a linear sequence of elements, where each element points to the next one rather than being stored in contiguous memory locations. This design allows for efficient insertions with O(1) complexity, outperforming arrays in dynamic scenarios. However, accessing specific elements requires O(n) time, which is less efficient compared to arrays' O(1) random access.

Types of Linked Lists

Singly Linked List

Each node contains data and a reference to the subsequent node, forming a unidirectional chain.

Doubly Linked List

Nodes maintain three components: the value, a pointer to the previous node, and another to the next node, enabling bidirectional traversal.

Circular Linked List

By connecting the last node back to the first, a circular structure is formed where traversal can continue indefinitely.

Common Problem Patterns

• Basic operasions: insertion, deletion, modification, and retrieval
• List reversal using recursion or iteration
• Merging multiple lists

Key Implementation Strategies

• Employ a sentinel node to simplify edge cases and maintain consistent indexing behavior similar to arrays
• When working with current.Next references, treat them as atomic units or use tempoarry variables for clarity
• Always locate the predecessor node before performing modifications

Designing a Complete Linked List Structure

type LinkedList struct {
    length int
    start  *Node
}

type Node struct {
    Value int
    Next  *Node
}

func NewLinkedList() LinkedList {
    return LinkedList{
        start: &Node{}, // Sentinel node simplifies operations
        length: 0,
    }
}

func (list *LinkedList) GetValue(position int) int {
    if position < 0 || position >= list.length {
        return -1
    }
    
    current := list.start
    for step := 0; step <= position; step++ {
        current = current.Next
    }
    return current.Value
}

func (list *LinkedList) InsertAtBeginning(value int) {
    list.InsertAtPosition(0, value)
}

func (list *LinkedList) Append(value int) {
    list.InsertAtPosition(list.length, value)
}

func (list *LinkedList) InsertAtPosition(position int, value int) {
    if position > list.length {
        return
    }
    
    if position < 0 {
        position = 0
    }
    
    predecessor := list.start
    for step := 0; step < position; step++ {
        predecessor = predecessor.Next
    }
    
    newNode := &Node{
        Value: value,
        Next:  predecessor.Next,
    }
    
    predecessor.Next = newNode
    list.length++
}

func (list *LinkedList) RemoveAtPosition(position int) {
    if position < 0 || position >= list.length {
        return
    }
    
    list.length--
    predecessor := list.start
    for step := 0; step < position; step++ {
        predecessor = predecessor.Next
    }
    
    predecessor.Next = predecessor.Next.Next
}

Removing Specific Values from a List

To eliminate nodes containing target values, we traverse the list while maintaining references to both current and previous nodes:

func FilterValues(head *Node, target int) *Node {
    sentinel := &Node{Next: head}
    previous := sentinel
    current := sentinel.Next
    
    for current != nil {
        if current.Value == target {
            previous.Next = current.Next
        } else {
            previous = current
        }
        current = current.Next
    }
    
    return sentinel.Next
}

Reversing List Direction

The reversal process involves iteratively redirecting node pointers:

func ReverseSequence(head *Node) *Node {
    var prior *Node
    
    for head != nil {
        following := head.Next
        head.Next = prior
        prior = head
        head = following
    }
    
    return prior
}

Swapping Adjacent Pairs

For pairwise exchanges, we utilize a sentinel node to handle the initial pair uniformly:

func SwapAdjacentPairs(head *Node) *Node {
    sentinel := &Node{Next: head}
    current := sentinel
    
    for current.Next != nil && current.Next.Next != nil {
        first := current.Next
        second := current.Next.Next
        
        current.Next = second
        first.Next = second.Next
        second.Next = first
        current = first
    }
    
    return sentinel.Next
}

Removing Nth Node from End

Using two pointers with an offset enables single-pass identification of target nodes:

func RemoveFromEnd(head *Node, distance int) *Node {
    sentinel := &Node{Next: head}
    ahead, behind := head, sentinel
    
    for step := 0; step < distance; step++ {
        ahead = ahead.Next
    }
    
    for ahead != nil {
        ahead = ahead.Next
        behind = behind.Next
    }
    
    behind.Next = behind.Next.Next
    return sentinel.Next
}