Golang Linked List | Data Structure

In this Blog, We will learn about one of the Data Structures in Golang that is Linked List. We will learn creation of nodes, linking of nodes and functions based on Golang Linked List.

Before Learning Linked List you make sure the Golang Basics are clear and should have knowledge about Golang pointers.

What is a Linked List?

A Linked List is a linear Data Structure but not doesn’t have continuous memory addresses like Arrays or Slices. Linked Lists are Dynamic in nature.

In Golang Arrays we have to give size of the array while declaration, slice in golang uses arrays under the hood.

The Linked List is a Dynamic Data Structure, it occupies memory only for the stored data.

Golang Node Struct

type node struct {
	data int
	next *node
}

The Node Struct contains two fields one of type integer that contains the data and the “next” field that holds the memory address of the next Node.

node := &node{data: 20}

Node struct is initialized with an ampersand sign in the above code (main Function), this is because the node variable will then be passed to the pushback method which will link this node in the linked list.

Golang Linked List Struct

type linkedList struct {
	length int
	head   *node
	tail   *node
}

The Linked List Struct contains the length of the list, the head node and the tail node.

Length field in the Linked List Struct stored the length of the linked list.

The Head field of Node Type stores the memory address of the head or the first node of the linked list.

The tail field in Linked list of the Node type stored the memory address of the last node in the linked list.

Linked List Struct Initialization in Main Function.

list := linkedList{}

Length of the Linked List

func (l linkedList) Len() int {
	return l.length
}

This method returns the Length of the Linked List.

Golang Linked List Display

func (l linkedList) Display() {
	for l.head != nil {
		fmt.Printf("%v -> ", l.head.data)
		l.head = l.head.next
	}
	fmt.Println()
}

In order to print the linked list, we have to traverse the whole linked list when the head of the link list becomes nil the loop exits.

Golang Linked List PushBack

func (l *linkedList) PushBack(n *node) {
	if l.head == nil {
		l.head = n
		l.tail = n
		l.length++
	} else {
		l.tail.next = n
		l.tail = n
		l.length++
	}
}

The PushBack Method takes a node as input and links it to the linked list.

If the linked list is empty, it makes the incoming node as the first node, and the head and tail both starts pointing at the node. The Length of the linked list is increased by 1.

When the head node is already present the else part executes and the tail node’s next field stores the memory address of the incoming node and the tail starts pointing at the node.

Main Function code for the pushback function.

list.PushBack(node)

Delete a Node of Linked List in Golang

func (l *linkedList) Delete(key int) {

	if l.head.data == key {
		l.head = l.head.next
		l.length--
		return
	}
	var prev *node = nil
	curr := l.head
	for curr != nil && curr.data != key {
		prev = curr
		curr = curr.next
	}
	if curr == nil {
		fmt.Println("Key Not found")
		return
	}
	prev.next = curr.next
	l.length--
	fmt.Println("Node Deleted")
}

This Function deletes a node of the linked list. The function takes a key as an input and searches the key in the linked list if the node is found with the data it deletes the node.

Main Function Implementation.

func main() {
	list := linkedList{}
	node1 := &node{data: 20}
	node2 := &node{data: 30}
	node3 := &node{data: 40}
	node4 := &node{data: 50}
	node5 := &node{data: 70}
	list.PushBack(node1)
	list.PushBack(node2)
	list.PushBack(node3)
	list.PushBack(node4)
	list.PushBack(node5)
	fmt.Println("Length = ", list.Len())
	list.Display()
	list.Delete(40)
	fmt.Println("Length = ", list.Len())
	list.Display()

}

Output:

Length = 5
20 -> 30 -> 40 -> 50 -> 70 ->
Node Deleted
Length = 4
20 -> 30 -> 50 -> 70 ->

Linked List Front and Back Value

func (l linkedList) Front() (int, error) {
	if l.head == nil {
		return 0, fmt.Errorf("Cannot Find Front Value in an Empty linked list")
	}
	return l.head.data, nil
}

func (l linkedList) Back() (int, error) {
	if l.head == nil {
		return 0, fmt.Errorf("Cannot Find Front Value in an Empty linked list")
	}
	return l.tail.data, nil
}

These two methods Front and Back respectively return the first node and the last node of the linked list. If the linked list is empty it returns an error.

Linked List Reverse Function

func (l *linkedList) Reverse() {
	curr := l.head
	l.tail = l.head
	var prev *node
	for curr != nil {
		temp := curr.next
		curr.next = prev
		prev = curr
		curr = temp
	}
	l.head = prev
}

The Reverse Method reverses the linked list.

Main function implementation.

func main() {
	list := linkedList{}
	node1 := &node{data: 20}
	node2 := &node{data: 30}
	node3 := &node{data: 40}
	node4 := &node{data: 50}
	node5 := &node{data: 70}
	list.PushBack(node1)
	list.PushBack(node2)
	list.PushBack(node3)
	list.PushBack(node4)
	list.PushBack(node5)
	fmt.Println("Length = ", list.Len())
	list.Display()
	fmt.Println("Length = ", list.Len())
	list.Reverse()
	list.Display()

}

Output:

Length = 5
20 -> 30 -> 40 -> 50 -> 70 ->
Length = 5
70 -> 50 -> 40 -> 30 -> 20 ->

Golang Linked List Implementation Full Code

package main

import (
	"fmt"
)

type node struct {
	data int
	next *node
}

// LinkedList is a linked list
type linkedList struct {
	length int
	head   *node
	tail   *node
}

// Len Function returns Length of the LinkedList
func (l *linkedList) Len() int {
	return l.length
}

// PushBack Function inserts a new node at the end of the LinkedList
func (l *linkedList) PushBack(n *node) {
	if l.head == nil {
		l.head = n
		l.tail = n
		l.length++
	} else {
		l.tail.next = n
		l.tail = n
		l.length++
	}
}

func (l linkedList) Display() {
	for l.head != nil {
		fmt.Printf("%v -> ", l.head.data)
		l.head = l.head.next
	}
	fmt.Println()
}

func (l linkedList) Front() (int, error) {
	if l.head == nil {
		return 0, fmt.Errorf("Cannot Find Front Value in an Empty linked list")
	}
	return l.head.data, nil
}

func (l linkedList) Back() (int, error) {
	if l.head == nil {
		return 0, fmt.Errorf("Cannot Find Front Value in an Empty linked list")
	}
	return l.tail.data, nil
}

func (l *linkedList) Reverse() {
	curr := l.head
	l.tail = l.head
	var prev *node
	for curr != nil {
		temp := curr.next
		curr.next = prev
		prev = curr
		curr = temp
	}
	l.head = prev
}

func (l *linkedList) Delete(key int) {

	if l.head.data == key {
		l.head = l.head.next
		l.length--
		return
	}
	var prev *node = nil
	curr := l.head
	for curr != nil && curr.data != key {
		prev = curr
		curr = curr.next
	}
	if curr == nil {
		fmt.Println("Key Not found")
		return
	}
	prev.next = curr.next
	l.length--
	fmt.Println("Node Deleted")

}

func main() {
	list := linkedList{}
	node1 := &node{data: 20}
	node2 := &node{data: 30}
	node3 := &node{data: 40}
	node4 := &node{data: 50}
	node5 := &node{data: 70}
	list.PushBack(node1)
	list.PushBack(node2)
	list.PushBack(node3)
	list.PushBack(node4)
	list.PushBack(node5)
	fmt.Println("Length = ", list.Len())
	list.Display()
	list.Delete(40)
	list.Reverse()
	fmt.Println("Length = ", list.Len())
	list.Display()
	front, _ := list.Front()
	back, _ := list.Back()
	fmt.Println("Front = ", front)
	fmt.Println("Back = ", back)

}

Output:

Length =  5
20 -> 30 -> 40 -> 50 -> 70 ->
Node Deleted
Length =  4
70 -> 50 -> 30 -> 20 ->
Front =  70
Back =  20

Hope you like it!

Learn about Golang’s Container/list Package for learning about the doubly-linked lists.