Golang Linked List Implementation

LinkedList is a sequence of nodes that have properties and a reference to the next node in the sequence. It is a linear data structure that is used to store data. The data structure permits the addition and deletion of components from any node next to another node. They are not stored contiguously in memory, which makes them different arrays.

The first node of the list is called an head, and the last node of the list is called a tail. The last node of the list contains a pointer to the null. Each node in the list can be accessed linearly by traversing through the list from head to tail.

Golang Linked List Implementation

The following source code shows the complete implementation of LinkedList in Golang:

package main

// importing fmt package
import (
	"fmt"
)

//Node class
type Node struct {
	property int
	nextNode *Node
}

// LinkedList class
type LinkedList struct {
	headNode *Node
}

//AddToHead method of LinkedList class
func (linkedList *LinkedList) AddToHead(property int) {
	var node = &Node{}
	node.property = property
	node.nextNode = nil

	if linkedList.headNode != nil {
		//fmt.Println(node.property)
		node.nextNode = linkedList.headNode
	}

	linkedList.headNode = node

}

//NodeWithValue method returns Node given parameter property
func (linkedList *LinkedList) NodeWithValue(property int) *Node {
	var node *Node
	var nodeWith *Node
	for node = linkedList.headNode; node != nil; node = node.nextNode {
		if node.property == property {
			nodeWith = node
			break
		}
	}
	return nodeWith
}

//AddAfter method  adds a node with nodeProperty after node with property
func (linkedList *LinkedList) AddAfter(nodeProperty int, property int) {
	var node = &Node{}
	node.property = property
	node.nextNode = nil

	var nodeWith *Node

	nodeWith = linkedList.NodeWithValue(nodeProperty)
	if nodeWith != nil {
		//fmt.Println(node.property)
		node.nextNode = nodeWith.nextNode
		nodeWith.nextNode = node
	}

}

//LastNode method returns the last Node
func (linkedList *LinkedList) LastNode() *Node {
	var node *Node
	var lastNode *Node
	for node = linkedList.headNode; node != nil; node = node.nextNode {
		if node.nextNode == nil {
			lastNode = node
		}
	}
	return lastNode
}

//AddToEnd method adds the node with property to the end
func (linkedList *LinkedList) AddToEnd(property int) {
	var node = &Node{}
	node.property = property
	node.nextNode = nil

	var lastNode *Node

	lastNode = linkedList.LastNode()

	if lastNode != nil {
		lastNode.nextNode = node
	}

}

//IterateList method iterates over LinkedList
func (linkedList *LinkedList) IterateList() {

	var node *Node
	for node = linkedList.headNode; node != nil; node = node.nextNode {
		fmt.Println(node.property)

	}
}

// main method
func main() {

	var linkedList LinkedList

	linkedList = LinkedList{}

	linkedList.AddToHead(1)
	linkedList.AddToHead(3)
	linkedList.AddToEnd(5)
	linkedList.AddAfter(1, 7)
	//fmt.Println(linkedList.headNode.property)

	linkedList.IterateList()

}


The main() method adds 1 and 3 to the head of the linked list. 5 is added to the end. 7 is added after 1. The linked list will be 3, 1, 7, and 5.

Output:

3
1
7
5

Let's understand the above LinkedList implementation.

We have created a Node class:

//Node class
type Node struct {
	 property int
	 nextNode *Node
}

The LinkedList class has the headNode pointer as its property. By traversing to nextNode from headNode, you can iterate through the linked list, as shown in the following code:


// LinkedList class
type LinkedList struct {
 	headNode *Node
}

The AddToHead() method adds the node to the start of the linked list:


//AddToHead method of LinkedList class
func (linkedList *LinkedList) AddToHead(property int) {
	var node = &Node{}
	node.property = property
	node.nextNode = nil

	if linkedList.headNode != nil {
		//fmt.Println(node.property)
		node.nextNode = linkedList.headNode
	}

	linkedList.headNode = node
}

The LastNode() method of LinkedList returns the node at the end of the list:


//LastNode method returns the last Node
func (linkedList *LinkedList) LastNode() *Node {
	var node *Node
	var lastNode *Node
	for node = linkedList.headNode; node != nil; node = node.nextNode {
		if node.nextNode == nil {
			lastNode = node
		}
	}
	return lastNode
}

The AddToEnd() method adds the node at the end of the list:


//AddToEnd method adds the node with property to the end
func (linkedList *LinkedList) AddToEnd(property int) {
	var node = &Node{}
	node.property = property
	node.nextNode = nil

	var lastNode *Node

	lastNode = linkedList.LastNode()

	if lastNode != nil {
		lastNode.nextNode = node
	}

}

The NodeWithValue() method of LinkedList returns the node with the property value:


//NodeWithValue method returns Node given parameter property
func (linkedList *LinkedList) NodeWithValue(property int) *Node {
	var node *Node
	var nodeWith *Node
	for node = linkedList.headNode; node != nil; node = node.nextNode {
		if node.property == property {
			nodeWith = node
			break
		}
	}
	return nodeWith
}

The AddAfter() method adds the node after a specific node:


//AddAfter method  adds a node with nodeProperty after node with property
func (linkedList *LinkedList) AddAfter(nodeProperty int, property int) {
	var node = &Node{}
	node.property = property
	node.nextNode = nil

	var nodeWith *Node

	nodeWith = linkedList.NodeWithValue(nodeProperty)
	if nodeWith != nil {
		//fmt.Println(node.property)
		node.nextNode = nodeWith.nextNode
		nodeWith.nextNode = node
	}

}

The IterateList() method of the LinkedList class iterates from the headNode property and prints the property of the current head node.


//IterateList method iterates over LinkedList
func (linkedList *LinkedList) IterateList() {

	var node *Node
	for node = linkedList.headNode; node != nil; node = node.nextNode {
		fmt.Println(node.property)

	}
}

Comments