Linked Lists as data structures are very powerful and provide a lot of flexibility and enhanced performance especially in systems with memory constraints towards continuous memory allocation because linked lists do not need a large continuous block of memory to be allocated in order to run the program.
Many programs within the operating systems use linked lists in some form instead of arrays for efficient runtime and memory allocation. A classic example being a least recently used (LRU) cache used in paging which uses a combination of doubly linked lists and maps.
There are numerous operations which can be performed on linked lists, for the sake of not bloating up this article we will be using only 3 basic operations, which are
Traverse: Go to each node and print the value contained by that node.
Insert: Inserts a new node after a particular node.
Delete: Delete the node after a particular node and in case there is no node to delete, do nothing.
Note: We will be using the getter-setter pattern to read and write the fields within the linked list node and not directly reference them.
We will start with defining the interface for our implementation.
type IListNode interface {
GetValue() int
SetValue(value int)
GetNextNode() IListNode
SetNextNode(nextNode IListNode)
InsertNextNode(nextNode IListNode)
DeleteNextNode()
}
After defining the interface, we need to declare the struct which will be an implementation of the above interface.
type ListNode struct{
value int
next IListNode
}
After declaring the struct, we start with defining the getter-setter methods for the fields.
func (n *ListNode) GetValue() int {
return n.value
}
func (n *ListNode) SetValue(value int) {
n.value = value
}
func (n *ListNode) GetNextNode() IListNode {
return n.next
}
func (n *ListNode) SetNextNode(nextNode IListNode) {
n.next = nextNode
}
No comes the definition of the methods to perform the basic operations, i.e. Insert and Delete.
func (n *ListNode) InsertNextNode(nextNode IListNode) {
/* sets the next node address in the field of
the new node getting inserted */
nextNode.SetNextNode(n.GetNextNode())
//sets the next node address as the new node
n.SetNextNode(nextNode)
}
func (n *ListNode) DeleteNextNode() {
if n.GetNextNode()!=nil {
// setting the next node address by skipping one node
n.SetNextNode(n.GetNextNode().GetNextNode())
}
}
Do we need to deallocate the memory allocated to the list node getting deleted?
After defining two of the basic operations we will declare the function which traverses through the linked list and prints the values in the nodes.
func Traverse(listNode IListNode) {
for listNode!=nil {
fmt.Printf("%d -> ",listNode.GetValue())
listNode = listNode.GetNextNode()
}
fmt.Println("nil")
}
Example:
func main(){
head := new(ListNode)
head.SetValue(1)
Traverse(head) // prints 1 -> nil
node1 := new(ListNode)
node1.SetValue(3)
head.InsertNextNode(node1)
Traverse(head) // prints 1-> 3 -> nil
node2 := new(ListNode)
node2.SetValue(2)
head.InsertNextNode(node2)
Traverse(head) // prints 1 -> 2 -> 3 -> nil
node2.DeleteNextNode()
Traverse(head) // prints 1 -> 2 -> nil
}
Next Steps
Attempt the following problem on leetcode.com