Blog

DS with Go Part 2: Linked List Variants

· Updated

Data Structures with Go - Part 2: Linked List Variants

All code from this tutorial can be found here.

NOTE: In this tutorial, we will be borrowing heavily from the last tutorial on linked lists. Do read that in case you missed it here.

After completing this tutorial you should be able to:

  1. Create doubly & circular linked lists
  2. Perform insertion, deletion, and traversal operations on both these variants.

Doubly Linked Lists

Doubly linked lists have 2 pointersFigure 1: Doubly linked lists have 2 pointers.

Each node in a doubly linked list has 2 pointers, one pointing to its next node and one to its previous node. The first node has its previous pointer set to null and the last node has its next pointer set to null.

And.. that’s it basically.

Basic structure

// Doubly Linked List Structure.go
type DLNode struct {
	Data int
	Prev *DLNode
	Next *DLNode
}

In our definition, Prev points to the previous node and Next points to the next node in the list.

Traversal

// DL List traversal and length.go
func DisplayList(head *DLNode) {
	fmt.Printf("The list is: ")
	for ; head != nil; head = head.Next {
		fmt.Print(" -> ", head)
	}
	fmt.Println()
	fmt.Println()
}

func Length(head *DLNode) int {
	len := 0
	for ; head != nil; head = head.Next {
		len++
	}
	fmt.Println("Length = ", len)
	return len
}

Traversal and finding the length of a doubly linked list is the same as the singly linked version. Not much difference here.

Insertion

Inserting at the start:

Inserting a new node at the start of the list.Figure 2: Inserting a new node at the start of the list.

Insertion at the start of the list is also the same as in the case of a singly linked list. The only addition is changing the pointer Prev of the current start node to point to the new node.

// InsertAtStart.go
func InsertAtStart(head **DLNode, x int) {
	// We dont need to explicitly initialize Next & Prev. They will be given the zero value automatically.
	tmp := &DLNode{Data: x}
	fmt.Println("\nInserting", tmp, "at the start")
	if *head == nil {
		*head = tmp
		return
	}
	tmp.Next = *head
	(*head).Prev = tmp
	*head = tmp
}

To make the code more readable, I now create new nodes using &Node{} rather than Node{} .

Inserting at the end:

Inserting a new node at the end of the list.Figure 3: Inserting a new node at the end of the list.

This is similar to inserting nodes at the end of singly linked lists. The only addition is that the Prevpointer of the new node will now point to the last node of the list.

// InsertAtEnd.go
func InsertAtEnd(head **DLNode, x int) {
	tmp := &DLNode{Data: x}
	fmt.Println("Inserting", tmp, "at the end")
	if *head == nil {
		*head = tmp
	} else {
		p := *head
		for ; p.Next != nil; p = p.Next {
		}
		p.Next = tmp
		tmp.Prev = p
	}
}

Inserting at a specific position:

To insert the new node at a specific position, 4 pointers are changed.Figure 4: To insert the new node at a specific position, 4 pointers are changed.

Once again we borrow the strategy of finding a node at a specific position from singly linked lists. The new node is inserted before the current node at position p . After insertion, the new node is at position p and the node previously at p is now at the position p+1 .

4 pointers are changed when inserting a node at a specific position:

  1. NewNode.Next points to the node at position p

  2. NewNode.Prev points to the node at position p-1

  3. NodeAtP.Prev points to the new node

  4. NodeBeforeP.Next points to the new node

// InsertAtP.go
func InsertAtP(head **DLNode, p int, x int) {
	if p < 1 {
		fmt.Println("Positions start at 1. Invalid Position.")
		return
	}

	if p == 1 {
		InsertAtStart(head, x)
		return
	}
	if *head == nil {
		fmt.Println("Position Invalid.")
		return
	}
	current := *head
	i := 1
	// Find the penultimate node
	for i < p-1 && current.Next != nil {
		current = current.Next
		i++
	}
	// This means we reached the end of the list and i != p-1
	if i < p-1 {
		fmt.Println("Invalid Position")
		return
	}
	tmp := &DLNode{Data: x}
	fmt.Println("Inserting", tmp, "at position", p)
	tmp.Prev = current
	tmp.Next = current.Next
	if current.Next != nil {
		current.Next.Prev = tmp
	}
	current.Next = tmp
}

Here we find the penultimate node (i.e. the one right before the insertion point. Penultimate here is with respect to the point of insertion.) which in this case is currentand change its Next pointer to point to the new node i.e. current.Next = tmp (line 34).

But before we do that, we need to change the Prev pointer of the node at position p i.e. current.Next.Prev to point to tmp. But we can’t do this if current.Next is nil which it will be if the insertion point is at 1+Length of the list. Hence lines 31–34.

Putting together the functions above and executing would result in an output similar to the one below. Code for this sample execution is here.

Inserting &{1 <nil> <nil>} at the start
The list is: -> &{1 <nil> <nil>}

Inserting &{2 <nil> <nil>} at the end
The list is: -> &{1 <nil> 0xc00000c0a8} -> &{2 0xc00000c060 <nil>}

Inserting &{3 <nil> <nil>} at the end
The list is: -> &{1 <nil> 0xc00000c0a8} -> &{2 0xc00000c060 0xc00000c108} -> &{3 0xc00000c0a8 <nil>}

Inserting &{4 <nil> <nil>} at position 4
The list is: -> &{1 <nil> 0xc00000c0a8} -> &{2 0xc00000c060 0xc00000c108} -> &{3 0xc00000c0a8 0xc00000c180} -> &{4 0xc00000c108 <nil>}

Have a look at the Prev and Next addresses in the output above. It’s very cool to see the actual addresses used by the nodes on the hardware.

Deletion

Deleting the first node:

// DeleteFirst.go
func DeleteFirst(head **DLNode) {
	if *head == nil {
		fmt.Println("\nList empty")
		return
	}
	fmt.Println("\nDeleting first Node: ", *head)
	// We change head to point to the next Node
	*head = (**head).Next
	// To remove all references to the deleted node, set the Prev pointer of head to nil
	if *head != nil {
		(**head).Prev = nil
	}
}

In addition to moving the head pointer to the 2nd node as in the case of a singly linked list, we change the Prev pointer of the 2nd node to nil. Easy!!!

Deleting the last node:

// DeleteLast.go
func DeleteLast(head **DLNode) {
	if *head == nil {
		fmt.Println("\nList is empty")
		return
	}
	// If there is only 1 node in the list
	if (*head).Next == nil {
		*head = nil
		return
	}
	current := *head
	// Find the last node
	for current.Next != nil {
		current = current.Next
	}
	fmt.Println("\nDeleting last node: ", current)
	// Change the Next pointer of the penultimate node to nil
	current = current.Prev
	current.Next = nil
}

The logic here is the same as a singly linked list. Find the penultimate node, change it’s Next pointer to nil.

Deleting at a specific position:

Logic for deleting a node at a specific positionFigure 5: Logic for deleting a node at a specific position

Referring to the diagram above, let’s say we want to delete Node 2. All we need to do is change Node1.Next to point to Node 3 and change Node3.Prev to point to Node 1.

// DeleteAtP.go
func DeleteAtP(head **DLNode, p int) {
	// Edge case 1: Positions less than 1
	if p < 1 {
		fmt.Println("Positions start from 1. Position Invaid.")
		return
	}
	// Edge case 2: List is empty
	if *head == nil {
		fmt.Println("List empty")
		return
	}
	// Edge case 3: Deletion position is 1
	if p == 1 {
		DeleteFirst(head)
		return
	}

	current := *head
	i := 1
	// Find node to delete
	for i < p && current.Next != nil {
		current = current.Next
		i++
	}
	// Edge case 4: Position exceeds length of the list
	if i < p {
		fmt.Println("Position Invalid")
		return
	}
	previousNode := current.Prev
	nextNode := current.Next
	previousNode.Next = nextNode
	// Edge case 5: The node to delete is the last in the list. If it is nextNode will be nil
	if nextNode != nil {
		nextNode.Prev = previousNode
	}
}

There are 5 edge cases we need to consider:

  1. Deletion position < 1: These are invalid (Lines 3–5).

  2. Empty list (Lines 8–10).

  3. Deletion position is at the start of the list: In this case, we can reuse the DeleteFirst function from the previous section (Lines 13–15).

  4. Deletion position exceeds the length of the list (Lines 26–28)

  5. The node to delete is the last in the list: In this case, there is no node after and we can’t change nextNode.Prev to point to the previousNode .

Note: Doubly linked lists have 2 pointers. Take care to change them both when inserting or deleting elements.

Deleting the entire list:

The logic is exactly the same as singly linked lists.

Borrowing some logic from singly linked lists.

Circular Linked Lists

The last node points to the first making the list circular.Figure 6: The last node points to the first making the list circular.

Circular linked lists don’t have an ‘end’ in the sense that there is no node that points to null. All nodes point to the next in line. The last node points back to the start of the list which makes the list circular.

We now look at the basic ops of circular linked lists.

Basic Structure:

The basic structure is exactly the same as a singly linked list.

There is always one node that points to the start of the list. This node is the last node in the list.

Traversal:

If there is no last node then how do we know when to stop the traversal loop??

We use a 2 pointer approach. One stays put pointing to the symbolic start of the list, the other is used to traverse the list. When the second pointer (current in this case) and the head point to the same node, we have successfully traversed the list.

This logic is used for both displaying the list as well as finding the length of the list.

// TraversalOps.go
func DisplayList(head *Node) {
	fmt.Printf("The list is: ")
	current := head
	if current == nil {
		fmt.Println("empty.")
		return
	} else {
		fmt.Print(" -> ", current)
		current = current.Next
		for ; current != head; current = current.Next {
			fmt.Print(" -> ", current)
		}
		fmt.Println()
		fmt.Println()
	}
}

func Length(head *Node) int {
	current := head
	if current == nil {
		return 0
	} else {
		len := 1
		current = current.Next
		for ; current != head; current = current.Next {
			len++
		}
		return len
	}
}

Insertion

For any insertion op, we will in the worst case need to traverse the whole list. But why??

  1. Inserting at the start: Need to change the last node to point to the new node at the start.

  2. Inserting at the end: Need to find the last node, make it point to the new node & make the new node point to the start of the list.

  3. Inserting at a specific position: If the insertion point is the start or the end of the list, we have to traverse the entire list anyways. If the insertion point is somewhere in between, only then will we not have to traverse the entire list.

Inserting at the start:

Make the last node point to the new one. Make the new node point to the start.Figure 7: Make the last node point to the new one. Make the new node point to the start.

// InsertAtStart.go
func InsertAtStart(head **Node, x int) {
	// Create new node
	tmp := &Node{Data: x}
	tmp.Next = tmp

	fmt.Println("\nInserting", tmp, "at the start ")
	if *head == nil {
		*head = tmp
		return
	}
	p := *head
	for ; p.Next != *head; p = p.Next {
	}
	p.Next = tmp
	tmp.Next = *head
	*head = tmp
}

To insert a new node at the start, first find the last node using the 2 pointer approach. Then make the last node point to the new node and the new node point to the start of the list (Lines 11–16).

Inserting at the end:

Make the new node point to the start of the list. Make the last node point to the new node.Figure 8: Make the new node point to the start of the list. Make the last node point to the new node.

// InsertAtEnd.go
func InsertAtEnd(head **Node, x int) {
	// Create a new node & make it point to itself.
	tmp := &Node{Data: x}
	tmp.Next = tmp

	fmt.Println("\nInserting", tmp, "at the end")
	if *head == nil {
		*head = tmp
	} else {
		p := *head
		// Find the last node
		for ; p.Next != *head; p = p.Next {
		}
		p.Next = tmp
		// Make the new node point to head
		tmp.Next = *head
	}
}

The logic here is simple. Make the new node point to the start of the list. Find the last node (the last node always points to the start of the list). Make the last node point to the new node (Lines 10–16).

Inserting at a specific position:

// InsertAtP.go
func InsertAtP(head **Node, p int, x int) {
	if p < 1 {
		fmt.Println("\nPositions start at 1. Invalid input position.")
		return
	}

	if p == 1 {
		InsertAtStart(head, x)
		return
	}
	// If insertion point is not the start and the list is empty, insertion point is invalid.
	if *head == nil {
		fmt.Println("\nInvalid Position.")
		return
	}

	current := *head
	i := 1
	for i < p-1 && current.Next != *head {
		current = current.Next
		i++
	}
	if i < p-1 {
		fmt.Println("\nInvalid Position")
		return
	}
	tmp := &Node{Data: x}
	tmp.Next = tmp
	fmt.Println("\nInserting", tmp, "at the position", p)
	tmp.Next = current.Next
	current.Next = tmp
}

The logic for inserting at a specific position is the same as the singly linked list.

As you see, a lot of the logic here is borrowed from or is the same as the previous article on singly linked lists.

Deletion:

Deleting from the start:

Make the last node point to the 2nd node in the list.Figure 9: Make the last node point to the 2nd node in the list.

To delete the first node, find the last node, make it point to the 2nd node in the list and change the head to point to the second node.

// DeleteFirst.go
func DeleteFirst(head **Node) {
	if *head == nil {
		fmt.Println("\nList empty")
		return
	}
	fmt.Println("\nDeleting first Node: ", *head)
	// Edge Case 1: Only one node exists in the list
	if (*head).Next == *head {
		*head = nil
		return
	}
	// Traverse to last node
	p := *head
	for ; p.Next != *head; p = p.Next {
	}
	p.Next = (*head).Next
	*head = (*head).Next
}

Deleting the last node:

Change the penultimate node to point to the head.Figure 10: Change the penultimate node to point to the head.

To delete the last node, find the penultimate node and make it point to the first node in the list. Super easy!!!

// DeleteLast.go
func DeleteLast(head **Node) {
	if *head == nil {
		fmt.Println("\nList is empty")
		return
	}
	// Edge Case 1: If there is only 1 node in the list
	if (*head).Next == *head {
		*head = nil
		return
	}
	current := (*head).Next
	previous := *head
	for current.Next != *head {
		previous = current
		current = current.Next
	}
	fmt.Println("\nDeleting last node: ", current)
	previous.Next = *head
	current.Next = nil
}

Delete at a specific position:

The logic here too is the same as a singly linked list.

// DeleteAtP.go
func DeleteAtP(head **Node, p int) {
	if p < 1 {
		fmt.Println("\nPositions start from 1. Cannot delete.")
		return
	}
	if *head == nil {
		fmt.Println("\nList is empty")
		return
	}
	if p == 1 {
		DeleteFirst(head)
		return
	}
	i := 1
	var previous *Node = nil
	current := *head
	for i < p && current.Next != *head {
		previous = current
		current = current.Next
		i++
	}
	if i < p {
		fmt.Println("Invalid position.")
		return
	}
	fmt.Println("Deleting", current, "at position", p)
	previous.Next = current.Next
	current = nil
}

Deleting the entire list:

// DeleteList.go
func DeleteList(head **Node) {
	fmt.Println("\nDeleting entire linkedlist")
	var aux *Node
	for *head != nil {
		aux = (*head).Next
		if aux == *head || aux == nil {
			*head = nil
			return
		}
		(*head).Next = nil
		*head = aux
	}
}

Just like singly and doubly linked lists, we use an auxiliary pointer to help traverse the list. And the similarities end there.

Here we change the Next pointer of each node to point to nil. This is to make sure that eventually there are no nodes that point to either themselves or to the start of the list. By doing this we make sure that the deletion loop is finite. Towards the end, the pointer aux will point to the first node in the list. But this time that node will point to nil and the block at lines 6–8 will cause the loop to exit.

A sample script to view the outputs of the insertion and deletion operations can be found here.

Putting insertion and deletion together would produce outputs like this:

Inserting &{1 0xc00018a190} at the start 
The list is:  -> &{1 0xc00018a190}

Inserting &{2 0xc00018a1c0} at the end
The list is:  -> &{1 0xc00018a1c0} -> &{2 0xc00018a190}

Inserting &{3 0xc00018a200} at the end
The list is:  -> &{1 0xc00018a1c0} -> &{2 0xc00018a200} -> &{3 0xc00018a190}

Inserting &{4 0xc00018a250} at the position 4
The list is:  -> &{1 0xc00018a1c0} -> &{2 0xc00018a200} -> &{3 0xc00018a250} -> &{4 0xc00018a190}

Deleting first Node:  &{1 0xc00018a1c0}
The list is:  -> &{2 0xc00018a200} -> &{3 0xc00018a250} -> &{4 0xc00018a1c0}

Deleting last node:  &{4 0xc00018a1c0}
The list is:  -> &{2 0xc00018a200} -> &{3 0xc00018a1c0}

Deleting &{3 0xc00018a1c0} at position 2
The list is:  -> &{2 0xc00018a1c0}

Deleting first Node:  &{2 0xc00018a1c0}
The list is: empty.

Pay attention to the addresses. Every new node when initialized points to itself. When inserted in the list, it points to the first node in the list. When deleting the addresses are changed accordingly to point to the next node in the list (which would be the first node for the node at the end of the list).

You should now be able to:

  1. Create doubly & circular linked lists

  2. Perform insertion, deletion, and traversal operations on both the list types

If you enjoyed reading this article or if it helped you in any way, a 👏 is appreciated. Do share this article with others who may be interested in the topic too.

Stay in touch with me on Linkedin and Twitter . Follow me on GitHub.