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)