What is a Linked List?

A linked list is a type of list. It keeps elements in a certain order but it uses a style that is different from usual lists. A Node is allocated for each element/item in the list. Each Node maintains a reference to its element and one or more references to neighboring Nodes to represent the linear order of the sequence. Elements of a linked list cannot be accessed by the typical number index method.

A Node

Let us view a Node as a packet or container. Depending on the type of linked list, a Node will hold its data or main element, a pointer to the next node on the list, and a pointer to the previous node on the list. The Node of a Singly Linked List will hold only two items. The main data element of the Node (usually Node.data), and a pointer to the next Node on the list (usually Node.next).

SINGLY LINKED LIST

A singly linked list like the name implies is for a list that is linked from one side, or by one direction (Not the music group). It is a collection of nodes that collectively form a linear(straight line) sequence. Each Node stores a reference to an object that is an element of the sequence(i.e the data of the Node) as well as a pointer to the next node on the list. If there is no next node on the list, the pointer references null or None. Below is the class declaration for a Node instance and An empty singly linked LinkedList.

class Node:
  def __init__(self, data, next):
    self.data = data
    self.next = next

class MyLinkedList:
  def __init__(self):
    self.head = None
    self.size = 0
    self.tail = None

The Head

The Head of a linked list is the first item in the linked list. If the head is None, this means that the linked list is empty.

The Tail

The Tail of a linked list is the last item in the linked list. It is the item whose next pointer references None, meaning that there is nothing after the Node. It is quite a hassle targeting the tail because this would mean moving from the head through every single item until the tail is located (This is called Traversing a linked list).

Inserting a new Node at the Tail of a Singly linked list

To insert a new node at the tail of a Singly linked list is to insert it at the end of the linked list. To do this, The following have to be in place already.

We have a Node class (This usually comes with the challenge, already available to use)
We have a linked list (may or may not be empty)
We have the current tail, i.e self.tail or we have the current head

Below is the pseudo-code to guide the process when you have the self.tail value:

Create a new node instance from the node class
If the current tail is None, this means the list is empty. We will set the current tail to our new node, i.e only one item in the list, this one item will serve as both the head and the tail, so we will also set tail equal to the head.
Else:
set the current self.tail.next to point to the new node, then set the self.tail value to the new node, and increase the node size by one.

def insert_at_tail(self, new_node):
    if self.tail == None:
      self.tail = new_node
      self.head = self.tail
    else:
      self.tail.next = new_node
      self.tail = new_node
    self.size+=1

Traversing a linked list

Traversing means visiting each node of the list once in order to perform some operation. But if you are given only the head value, you would need to transverse through the entire linked list until you find the last element. The code is shown below.

def insert_at_tail(self, new_node):
    if self.head == None:
      self.head = new_node
    else:
      current_head = self.head
      # traverse the linked list
      while current_head.next != None:
          current_head = current_head.next
     # break out of the loop
    current_head.next = new_node
    self.size+=1

The new node is now the tail, and your linked list is an item larger. A linked list does not have a predetermined list size. The size of the linked list at each point is the number of items in the linked list at that moment. Subsequently, we would look at inserting into other points in the list, deleting and reversing a linked list.

If you enjoyed reading this,

Thank You!

MergeMyPR