A linked list is a data structure which is made up of **nodes **connected in a chain-like manner.

Elements/nodes in a linked list are not stored in consecutive memory locations like in an array(such as python list). Instead, the elements are **scattered throughout the memory** and each nodes contains a pointer to the location of the next node in the list.

There are several types of linked lists depending on the relation between the nodes. In this article we will focus on **singly-linked lists**.

In a singly-linked list, each node has two parts:** a value** and **a pointer **to the next node in the list. The first node in the list is called the **head**, and the last node is called the **tail**. A **null **object is usually used to indicate the end of the list.

The figure below demonstrates the structure of a singly linked list.

Singly-linked lists allow traversal only in one direction. By starting from the head and moving to the next node via the link, we can reach the end of the list. However, there is no way of reaching the previous node and, therefore, traversal cannot happen backwards.

In most practical cases, a singly linked list is used to implement other data structures such as **stacks**, **queues**, and **trees**.

## Implement Stack using singly linked list

A stack is a data structure in which the last element to be inserted is also the first one to be removed. This is also known as the **List-In-First-Out(LIFO) **principle. A stack typically supports the following operations:

`push(e)` |
Pushes element `e` at the top of the stack. |

`pop()` |
removes an returns the element at the top. Raises an error if the stack is empty |

`top()` |
Returns the element at the top without removing it. Raises an error if the stack is empty. |

`is_empty()` |
Returns `True ` if the stack is empty, `False ` otherwise. |

`len()` |
Returns the number of elements in the stack. |

In this part we will implement a stack using a singly linked list.

We will implement a non-public subclass` _Node`

, to represent a node in the linked structure. The implementation of the `_Node`

class is as shown below:

The _Node class

```
class _Node:
def __init__(self, e, n):
self._element = e #Users element
self._next = n #The next node in the list
```

We will use the `_Node `

subclass for low-level operations. The final user will not interact with the class.

Implement the stack

```
#an exception to be raised by an empty stack
class Empty(Exception):
pass
class Stack:
class _Node:
def __init__(self, e, n):
self._element = e #Users element
self._next = n #The next node in the list
def __init__(self):
self._head = None #Reference the first node in the linked list
self._size = 0 #The number of elements in the stack
def __len__(self):
return self._size
def is_empty(self):
return len(self) == 0
def push(self, e):
#add a new element to the stack
self._head = self._Node(e, self._head)
self._size += 1
def top(self):
if self.is_empty():
raise Empty("Stack is empty.")
return self._head._element
def pop(self):
if self.is_empty():
raise Empty("Stack is empty.")
element = self._head._element
self._head = self._head._next # make the
self._size -= 1
return element
# test the stack
S = Stack()
S.push(10)
S.push(20)
S.push(30)
S.push(40)
S.push(50)
print("Size: ", len(S))
while not S.is_empty():
print(S.pop())
```

### Implement Queue using singly linked list

A queue is a type of data structure that follows the **First-Out-First-In(FIFO) **principle. This is where elements are added at one end and removed from the other. A queue supports the following operations:

`enqueue(e)` |
Add element e at the back of the queue. |

`dequeue()` |
Remove and return the element at the front of the queue. An exception is raised if empty. |

`first()` |
Return the first element without removing it. An exception is raised if empty. |

`is_empty()` |
Return `True` , if the queue is empty and `False ` otherwise. |

`len()` |
Return the number of elements in the queue. |

As we saw in the previous section, operations in a stack only happens at one end and we therefore only needed to track one end using the `_head `

variable. But in a queue, operations happen in both ends, as we are inserting in one end and removing from the other. We will, therefore, need to track the nodes at both ends.

The following snippet hows the implementation of a `Queue `

using singly-linked list.

Implement a Queue

```
#an exception to be raised by an empty Queue
class Empty(Exception):
pass
class Queue:
class _Node:
def __init__(self, e, n):
self._element = e #Users element
self._next = n #The next node in the list
def __init__(self):
self._head = None #Reference the first node
self._tail = None #refernce the last node
self._size = 0 #The number of elements in the queue
def __len__(self):
return self._size
def is_empty(self):
return len(self) == 0
def first(self):
if self.is_empty():
raise Empty("Queue is empty.")
return self._head._element
def enqueue(self, e):
#add a new element at the back
newnode = self._Node(e, None)
if self.is_empty():
self._head = newnode #if the queue is empty, the newnode becomes the head
else:
self._tail._next = newnode #if the queue is not empty, the last node points to the new node
self._tail = newnode #The new node becomes the tail
self._size += 1
def dequeue(self):
if self.is_empty():
raise Empty("Queue is empty.")
element = self._head._element
self._head = self._head._next # Make the next node the new head
self._size -= 1
return element
# test the stack
Q = Queue()
Q.enqueue(100)
Q.enqueue(200)
Q.enqueue(300)
Q.enqueue(400)
Q.enqueue(500)
print("Size: ", len(Q))
print(Q.first())
while not Q.is_empty():
print(Q.dequeue())
print("Size:", len(Q))
```