Linked List

Linked List is a list of uncontigous memory blocks.

Singly Linked List

Singly linked list has a pointer next pointing to the successor of the current node in the linked list.

G A A B B A->B next C C B->C next null null C->null next

Traversion

We can traverse through the linked list using a pointer.

G head head A A head->A B B A->B next C C B->C next null null C->null next

Reversion

We can use three pointer to reverse the order of the linked list.

cur, pre := head, nil
for cur.Next != nil {
    cur, cur.Next, pre = cur.Next, pre, cur
}

Before

G cur cur A A cur->A B B A->B pre pre null2 null pre->null2 C C B->C next null null C->null next

After

G null2 null pre pre A A null2->A cur cur B B cur->B C C B->C next pre->A null null C->null next

Nth node from the end

To find the Nth node from the tail of the linked list, we can use two pointers. First move the faster pointer N steps and then move both pointers until the faster pointer reach the end of the linked list. This can save us one time of full traversion.

slow, fast := head, head
for i := 0; i < N; i++ {
    fast = fast.Next
}
for fast.Next != nil {
    fast = fast.Next
    slow = slow.Next
}

Doubly Linked List

Doubly linked list has another pointer prev pointing to the predecessor of the current node as well.

G head head nullh null A A head->A tail tail C C tail->C nullt null B B A->B next A->B prev C->nullt next C->nullt prev nullh->A next nullh->A prev B->C next B->C prev

Circular Linked List

The head and tail of a circular linked list are linked together.

G A A B B A->B C C B->C D D C->D D->A

results matching ""

    No results matching ""