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. In a linked list, 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.

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 Head of a Singly linked list

To insert a new node at the head of a Singly linked list is to insert it at the beginning 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 head

Below is the pseudo-code to guide the process:

Create a new node instance from the node class
If the current head is None, we will set the current head to our new head node
Else: Set the next pointer of the new head node to point to the current head, then Set the current head to equal the new head node
Return the new head node

def insertNodeAtHead(current_head, data):
# Create a new node instance from the node class
    new_head = SinglyLinkedListNode(data)
# If the current head is None, set current head to new head node
    if current_head == None:
        current_head = new_head
# Else Set the next pointer of the new head node to the current head
    else:
        new_head.next = current_head
# Set the current head to equal the new head node
        current_head = new_head

    return new_head

The new head is now the new node that was created, 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