Linked List – Tlueaftab

“The list whose each element is connected through pointers.“

Why do we need linked list?

We need linked list because of given problem in Array.

“Arrays hold the consecutive places in the memory.”

When we delete/ insert an element from the array, we have to do shifting of elements from left to right or right to left depending upon the position of the element in array. It’s ok deleting the element from the ends of array but it can be costly in given scenario: –

Image-2: Array

Now, let’s perform delete(33);

Image-3: Array after deletion of element 33

Performing shifting of each elements from right to left can be time consuming and lead to inefficiency. Deletion takes O(N) time in case of arrays.

So, that’s the problem, let’s come to its solution.

Solution

This problem can be avoided by using linked list. Where the elements are not holding the consecutive memory, in other words, the elements are scattered across the memory. Where the position of next element can be recognized using the memory address wherever the element is placed.

Linked list actually is the collection of nodes, where each node consists of two parts: –

1^st: The value that it’s holding.
2^nd: The address of the next node

Object

Image-4: Node

Note: “next” is the pointer pointing to the next object.

Linked list through figures: –

Image-5 is showing the way linked list works. Head and current pointers are pointing to the 1st and current elements or nodes of the list respectively.

Make sure you understand!

Head: The pointer, pointing to the head/first element of the linked list.
Current = The pointer, pointing to the current object/element of linked list.

Explanation of linked list in computer memory

“head” is pointing to address 1062 that is holding address 1054, there is 2 at address 1054, now 1055, next to 1054 has the address 1051 and 6 is at 1051. Again, next to 1051, 1052 comes having address 1063 and 8 is at 1063. In this way, the elements are at the random position in the memory but pointers (2^nd part of the node) is directing towards the next element.

Linked list operations

The linked list data structure provides operations to work on the nodes inside the list.

Add Method

Let’s perform add(9) in the list (2, 6, 8, 7, 1).

So, here is the sequence to add 9 in the list: –

Creating a new node in the add function through C++ syntax: –

Node * newNode = new Node(9);

Steps in Image-7: –

The first step is to point next pointer of the new node (with data element as 9) to the node with data element as 7.
The second step is to point the next pointer of the node with data element 8 to the node the new node with data element 9.
The third step is to change the current pointer to point to the new node.

See Image-8 to understand the add method: –

headNode = The pointer, pointing to the 1^st node of the list.
currentNode = The Node at the current position.
lastCurrentNode = The node before the current node.

 void add(int addObject) {
	Node *newNode = new Node;
	newNode->set(addObject);
	if (currentNode != NULL) {
		newNode->setNext(currentNode->getNext());
		currentNode->setNext(newNode);
		lastCurrentNode = currentNode;
		currentNode = newNode;
	} else {
		newNode>setNext(NULL);
		headNode->setNext(newNode);
		lastCurrentNode = headNode;
		currentNode = newNode;
	}
	size++;
}