## LinearDataStructures

Linked List is a very commonly used linear data structure which consists of group of nodes in a sequence.

Each node holds its own data and the address of the next node hence forming a chain like structure.

Linked Lists are used to create trees and graphs.

• They are a dynamic in nature which allocates the memory when required.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.

•  The memory is wasted as pointers require extra memory for storage.
• No element can be accessed randomly; it has to access each node sequentially.
• Reverse Traversing is difficult in linked list.

• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list.
• In Linked Lists we don't need to know the size in advance.

There are 3 different implementations of Linked List available, they are:

Let's know more about them and how they are different from each other.

A linked list is a way to store a collection of elements. Like an array these can be character or integers. Each element in a linked list is stored in the form of a node.

Node:

A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.

A linked list is formed when many such nodes are linked together to form a chain. Each node points to the next node present in the order. The first node is always used as a reference to traverse the list and is called HEAD. The last node points to NULL.

Doubly linked list is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.

The two links help us to traverse the list in both backward and forward direction. But storing an extra link requires some extra space.

First we define the node.

Now we define our class Doubly Linked List. It has the following methods:

• delete: Removes the node
• forward_traverse: Traverse the list in forward direction
• backward_traverse: Traverse the list in backward direction

i)  Insert Data in the beginning

1.  The prev pointer of first node will always be NULL and next will point to front.
2. If the node is inserted is the first node of the list then we make front and end point to this node.
3. Else we only make front point to this node.

ii) Insert Data before a Node

Let’s say we are inserting node X before Y. Then X’s next pointer will point to Y and X’s prev pointer will point the node Y’s prev pointer is pointing. And Y’s prev pointer will now point to X. We need to make sure that if Y is the first node of list then after adding X we make front point to X.

iii) Insert Data after a Node

Let’s say we are inserting node Y after X. Then Y’s prev pointer will point to X and Y’s next pointer will point the node X’s next pointer is pointing. And X’s next pointer will now point to Y. We need to make sure that if X is the last node of list then after adding Y we make end point to Y.

iv) Insert Data in the end

1. The next pointer of last node will always be NULL and prev will point to end.
2. If the node is inserted is the first node of the list then we make front and end point to this node.
3. Else we only make end point to this node.

v) Remove a Node

Removal of a node is quite easy in Doubly linked list but requires special handling if the node to be deleted is first or last element of the list. Unlike singly linked list where we require the previous node, here only the node to be deleted is needed. We simply make the next of the previous node point to next of current node (node to be deleted) and prev of next node point to prev of current node. Look code for more details.

vi) Forward Traversal

Start with the front node and visit all the nodes until the node becomes NULL.

vii) Backward Traversal

Start with the end node and visit all the nodes until the node becomes NULL.

In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.

• The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
• Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance
• Circular Linked List can also be used to create Circular queue.  In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have its next point to the Head of the List. In Linear linked list the last Node simply holds NULL in its next pointer.

So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List.

i. Insertion at the Beginning

Steps to insert a Node at beginning:

2. When a new Linked List is instantiated, it just has the Head, which is Null.
3. Else, the Head holds the pointer to the first Node of the List.
4. When we want to add any Node at the front, we must make the head point to it.
5. And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL (in case of new List) or the pointer to the first Node of the List.
6. The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.

ii. Insertion at the End

Steps to insert a Node at the end: