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.
Top comments (0)