DEV Community

Cover image for Linked Lists : Go-lang and Python implementations.
myk_okoth_ogodo
myk_okoth_ogodo

Posted on

Linked Lists : Go-lang and Python implementations.

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())    
}
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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                                       
Enter fullscreen mode Exit fullscreen mode

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                                                            
Enter fullscreen mode Exit fullscreen mode

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())
}
Enter fullscreen mode Exit fullscreen mode

The above code results in

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

Program exited.
Enter fullscreen mode Exit fullscreen mode

Goodbye, see you soon.

Discussion (0)