Linked Lists : Go-lang and Python implementations.
Tags: go, data, python
Published: 2022-07-02 22:19:43

**Prelude**

Linked lists provide an alternative to array-based sequences i.e Lists . Both array based sequences and linked lists keep elements in a specific order, but the implementation of this feature varies widely between the two. 

Arrays provide a more centralized representation with one large chunk of memory capable of accommodating references to many elements. A linked list on the other hand relies of a more distributed architecture in which a lightweight object known as a node is used to represent each individual element of the linked list.

Each node in a linked list maintains a reference to its constituent element, and one or more references to neighboring nodes depending on whether its a single-linked list implementation or a double-linked list implementation. This  representation then allows us to collectively represent the linear order of our sequence.



## SINGLY-LINKED LISTS

Below we are going to give implementations of singly-linked list in both python and Go-lang as Queue, now this can be extended to Stacks and also trees for doubly linked lists.

**Memory use**

In comparison with doubly linked list, a singly linked list occupies less memory because it needs only one pointer to its successor. Each pointer variable  holds the address to an element, and the pointer occupies 4 bytes; therefore the memory space occupied by the pointer variable in the singly linked list is 4 bytes.  So memory also expands as per O(n) with n representing the number of elements and the  4 bytes being held constant for each pointer.

**Time complexity**

A singly linked list has an access time of 0(1), a search time of O(n), since we have to traverse the whole list from from first to last in one direction, it has an insertion time of O(n) and deletion time of O(n), in worst case and average case time.



**Golang  Singly-linked list Queue Implementation**

```
package main

import "fmt"

type Node struct {
	element int
	next    *Node
}
type GoLinkedQue struct {
	head *Node
	tail *Node
	size int
}

func (l *GoLinkedQue) Len() int {
	return l.size
}

func (l *GoLinkedQue) is_empty() bool {
	if l.size == 0 {
		return true
	}
	return false
}

func (l GoLinkedQue) First() (int, error) {
	if l.head == nil {
		return 0, fmt.Errorf("The Queue is empty !")
	}
	return l.head.element, nil
}

func (l GoLinkedQue) Last() (int, error) {
	if l.head == nil {
		return 0, fmt.Errorf("The Queue is empty !")
	}
	if l.size == 1 {
		return l.head.element, nil
	}
	return l.tail.element, nil
}

func (l *GoLinkedQue) dequeue() int {
	if l.is_empty() {
		fmt.Errorf("The Queue is empty !")
	}
	answer := l.head.element
	l.head = l.head.next
	l.size--
	if l.is_empty() {
		l.tail = nil
	}
	return answer

}
func (l *GoLinkedQue) enqueue(e int) *Node {
	newest := &Node{
		element: e,
		next:    nil,
	}
	if l.is_empty() {
		l.head = newest
	} else {
		l.tail.next = newest
	}
	l.tail = newest
	l.size++
	return newest
}

func main() {
	queue := GoLinkedQue{}
	queue.enqueue(100)
	queue.enqueue(200)
	queue.enqueue(300)
	queue.enqueue(400)
	queue.enqueue(500)
	queue.enqueue(600)
	firstval, _ := queue.First()
	lastval, _ := queue.Last()
	fmt.Println("Length = ", queue.Len())
	fmt.Println("First Element :", firstval)
	fmt.Println("Last Element  :", lastval)
	fmt.Println("Is Queue empty:", queue.is_empty())
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
        fmt.Println("Length =", queue.Len())
        fmt.Println("Is Queue empty:", queue.is_empty())    
}
```
If you run the above code in the golang-playground you get the results below

**output**

```
Length =  6
First Element : 100
Last Element  : 600
Is Queue empty: false
Program exited.
```


**single linked list implementation of a Queue structure in Python below**

```
  1 class PythonLinkedQueue:                                                                                                                                            
  2     """ A python implementation of a queue data structure using a 'singly linked-list' for storage."""
  3 
  4     class _Node:
  5         """"Lightweight, non-public class for storing  a single Nodes attributes."""
  6         __slots__ = "_element", "_next"
  7 
  8         
  9         def __init__(self, element, next):
 10             """"Instantiate a single Node object."""
 11             self._element = element
 12             self._next    = next
 13 
 14     
 15     def __init__(self):
 16         """Create an empty queue."""
 17         self._head = None
 18         self._tail = None
 19         self._size = 0
 20 
 21 
 22     def __len__(self):
 23         """Return the number of elements in the queue."""
 24         return self._size
 25 
 26     def is_empty(self):
 27         """Return True if the queue is empty. """
 28         return self._size == 0
 29 
 30     def first(self):
 31         """Return but do not remove the element that sits at the front of the queue."""
 32         if self.is_empty():
 33             raise Empty("The Queue is Empty!")
 34         return self._head._element
 35 
 36     def last(self):
 37         """ Return butt do not remove the element that sits at the back of  the queue."""
  38         if self.is_empty():
 39             raise Empty("The Queue is Empty!")
 40         elif self._size == 1:
 41             return self._head._element
 42         else:
 43             return  self._tail._element
 44 
 45     def dequeue(self):
 46         """Remove and return the first element of the queue(FIFO)"""
 47         if self.is_empty():
 48             raise Empty('Queue is empty')
 49         result =  self._head._element
 50         self._head = self._head._next
 51         self._size -= 1
 52         if self.is_empty():
 53             self._tail = None
 54         return result
 55 
 56     def enqueue(self, e):
 57         """Add an element to the back of the queue. """
 58         newest = self._Node(e, None)
 59         if self.is_empty():
 60             self._head = newest
 61         else:
 62             self._tail._next = newest
 63         self._tail = newest
 64         self._size += 1

```



## DOUBLY LINKED-LISTS

In a singly liked list each node maintains a reference to the node that is immediately after it. This asymmetry of the singly linked list comes with glaring limitations. Such as being unable to efficiently delete a node from the tail of the list or even we cannot perform an arbitrary node from the interior position of the if only given a reference to that node, because we cannot determine the node that immediately precedes the node we want to delete.

This is where a doubly-linked list enters the scene. To provide  greater symmetry we define a linked list in which each node keeps an explicit reference to the node before it and a reference to the node after it.

**Memory usage**

This list implementation holds two addresses in a single node, one address points to the previous Node and the other address to the next Node. Therefore the space occupied by the  two pointer variable is 8 bytes. The space is also bound to expand as per O(n), with n standing for the number of Nodes the linked list is currently holding, with each node eating up a constant of 8 bytes per Node.

**Time Complexities**

The doubly linked list has an insertion time complexity of O(1), a deletion time complexity of O(1), a search time complexity of O(n) and a access time complexity of O(n) both in average time and worst case time.

we will be implementing the deque data structure using doubly-linked lists. Deque is a queue-like data structure that supports insertion and deletion at both the front and the back of the queue.

**Header and Trailer Sentinels**

In order to avoid some special cases when operating near the boundaries of a doubly linked list, it helps to add special nodes at both ends of the list: a header node at the beginning of the list, and a trailer node at the end of the list. These “dummy” nodes are known as sentinels (or guards), and they do not store elements of the primary
sequence.


**Implementation In python**

```
  1 class _DoublyLinkedBase:
  2     """"A base class providing a doubly linked list representation."""                                                                                              
  3 
  4     class _Node:
  5         """A lightweight, non public class for storing a doubly linked node"""
  6         __slots__ = "_element","_next","_prev"
  7 
  8         def __init__(self, elment, prev, next):
  9             self._element = element
 10             self._prev    = prev
 11             self._next    = next
 12 
 13     def __init__(self):
 14         """Create ane empty list."""
 15 
 16         self._header  = self._Node(None, None, None)
 17         self._trailer = self._Node(None, None, None)
 18         self._header._next = self._trailer
 19         self._header._prev = self._header
 20         self._size = 0
 21 
 22     def  __len__(self):
 23         """Return the number of elements in the list."""
 24         return self._size
 25 
 26 
 27     def is_empty(self):
 28         """Return True if list is empty."""
 29         return self._size == 0
 30 
 31     def _insert_between(self, e, predecessor, successor):
 32         """Add element e between two existing nodes and return new node."""
 33         newest = self._Node(e, predecessor, successor)
 34         predecessor._next = newest
 35         successor._prev = newest
 36         self._size += 1                                                                                                                                             
 37         return newest 
 38 
 39     def _delete_node(self, node):
 40         """ Delete nonsentinel node from the list and return its element."""
 41         predecessor = node._prev
 42         successor = node._next
 43         predecessor._next = successor
 44         successor._prev = predecessor
 45         self._size -= 1
 46         element = node._element
 47         node._prev = node._next = node._element = None
 48         return element                                       
```


The above base class is inherited by the following class below:

```
  1 class LinkedDeque(_DoubleLinkedBase):
  2     """ Double-ended queue implemented based on a doubly linked list."""                                                                                            
  3 
  4     def first(self):
  5         """Return but do not remmove the element at the front of th deque."""
  6         if self.is_empty():
  7             raise Empty("Deque is empty")
  8         return self._header._next._element
  9 
 10 
 11     def last(self):
 12         """Return but do not remove the element at the back of the deque."""
 13         if self.is_empty():
 14             raise Empty("Deque is empty")
 15 
 16         return self._trailer._prev._element
 17 
 18 
 19     def insert_first(self, e):
 20         """Add an element to the front of the deque."""
 21         self._insert_between(e, self._header, self._header._next)
 22 
 23     def insert_last(self, e):
 24         """Add an element to the backk of the deque."""
 25         self._insert_between(e, self._trailer._prev, self._trailer)
 26 
 27     def delete_first(self):
 28         """Remove and return the lement from the front of the deque."""
 29         if self.is_empty():
 30             raise Empty("Deque is empty")
 31         return self._delete_node(self._header._next)
 32 
 33     def delete_last(self):
 34         """Remove and return the element from the back of the deque."""
 35         
 36         if self.is_empty():                                                                                                                                         
 37             raise Empty("Deque is empty") 
 38         return self._delete_node(self._trailer._prev)
 39                                                            
```



To implement the deque data structure using doubly linked lists in Go-lang we implement it as below

**Implementation in Golang**




```
package main

import "fmt"

type Node struct {
	element int
	prev    *Node
	next    *Node
}

type GoDoublyLinkedQue struct {
	header  *Node
	trailer *Node
	size int
}

func (l *GoDoublyLinkedQue) Len() int {
	return l.size
}

func (l *GoDoublyLinkedQue) is_empty() bool {
	if l.size == 0 {
		return true
	}
	return false
}

func (l GoDoublyLinkedQue) First() (int, error) {
	if l.header.next == l.trailer {
		return 0, fmt.Errorf("The Queue is empty !")
	}
	return l.header.next.element, nil
}

func (l GoDoublyLinkedQue) Last() (int, error) {
	if l.trailer.prev == l.header {
		return 0, fmt.Errorf("The Queue is empty !")
	}
	return l.trailer.prev.element, nil
}

func (l *GoDoublyLinkedQue) insert_between(e int, predecessor, sucessor *Node) *Node {
	newest := &Node{
		element: e,
		prev:    predecessor,
		next:    sucessor,
	}
	predecessor.next = newest
	sucessor.prev = newest
	l.size++
	return newest
}

func (l *GoDoublyLinkedQue) delete_node(node *Node) int {
	predecessor := node.prev
	sucessor := node.next
	predecessor.next = sucessor
	sucessor.prev = predecessor
	l.size--
	velement := node.element
	node.prev = nil
	node.next = nil
	node.element = 0
	return velement
}

func (l *GoDoublyLinkedQue) insert_first(e int) *Node {
	node := l.insert_between(e, l.header, l.header.next)
	return node

}

func (l *GoDoublyLinkedQue) insert_last(e int) *Node {
	node := l.insert_between(e, l.trailer.prev, l.trailer)
	return node
}

func (l *GoDoublyLinkedQue) delete_first() int {
	if l.is_empty() {
		fmt.Errorf("The Deque is empty")
	}
	element := l.delete_node(l.header.next)
	return element
}

func (l *GoDoublyLinkedQue) delete_last() int {
	if l.is_empty() {
		fmt.Errorf("The deque is empty")
	}
	element := l.delete_node(l.trailer.prev)
	return element
}

func main() {
	deque := GoDoublyLinkedQue{}
	deque.header = &Node{
		element: 0,
		prev:    nil,
		next:    nil,
	}
	deque.trailer = &Node{
		element: 0,
		prev:    nil,
		next:    nil,
	}
	deque.header.next = deque.trailer
	deque.trailer.prev = deque.header
	deque.insert_first(100)
	deque.insert_last(500)
	firstVal, _ := deque.First()
	lastVal, _ := deque.Last()
	fmt.Println("Length = ", deque.Len())
	fmt.Println("Is deque empty: ", deque.is_empty())
	fmt.Println("First Element :", firstVal)
	fmt.Println("Last Element  :", lastVal)
	deque.delete_last()
	deque.delete_first()
	fmt.Println("Is deque empty: ", deque.is_empty())
}
```
The above code results in

```
Length =  2
Is deque empty:  false
First Element : 100
Last Element  : 500
Is deque empty:  true

Program exited.
```
Goodbye, see you soon.