# Linked List - Easy Reference Guide

Everything has its own advantages and disadvantages and also every thing that is present will be used in some ways. I wanted to explain bit by bit about Linked List.

**Linked Lists**

A **linked list** is a linear data structure where each element is a separate object. **Linked list** elements are not stored at contiguous location; the elements are **linked** using pointers. Each node of a **list** is made up of two items - the data and a reference to the next node. The last node has a reference to null.

__Creation of node in Linked List using Python__

# Node class

**class** Node:

# Function to initialize the node object

**def** __init__(self, data):

self.data **=** data # Assign data

self.next **=** None # Initialize next as null

# Linked List class

**class** LinkedList:

# Function to initialize the Linked List object

**def** __init__(self):

self.head **=** None

__Adding a node to the linked list can be done in 3 ways__

At the front of the linked list

After a given node.

At the end of the linked list.

**1) Add a node at the front: (A 4 steps process)**

The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer, because push must change the head pointer to point to the new node

# This function is in LinkedList class

# Function to insert a new node at the beginning

**def** push(self, new_data):

# 1 & 2: Allocate the Node &

# Put in the data

new_node **=** Node(new_data)

# 3. Make next of new Node as head

new_node.next **=** self.head

# 4. Move the head to point to new Node

self.head **=** new_node

__2) Add a node after a given node: (5 steps process)__

We are given pointer to a node, and the new node is inserted after the given node.

# Inserts a new node after the given prev_node.

**def** insertAfter(self, prev_node, new_data):

# 1. check if the given prev_node exists

**if** prev_node **is** None:

**print** "The given previous node must inLinkedList."

**return**

# 2. Create new node &

# 3. Put in the data

new_node **=** Node(new_data)

# 4. Make next of new Node as next of prev_node

new_node.next **=** prev_node.next

# 5. make next of prev_node as new_node

prev_node.next **=** new_node

__3)Add a node at the end: (6 steps process)__

The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.

Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.

# This function is defined in Linked List class

# Appends a new node at the end. This method is

# defined inside LinkedList class shown above */

**def** append(self, new_data):

# 1. Create a new node

# 2. Put in the data

# 3. Set next as None

new_node **=** Node(new_data)

# 4. If the Linked List is empty, then make the

# new node as head

**if** self.head **is** None:

self.head **=** new_node

**return**

# 5. Else traverse till the last node

last **=** self.head

**while** (last.next):

last **=** last.next

# 6. Change the next of last node

last.next **=** new_node

__Implementation of Linked List methodologies:__

We can implement the linked list using 2 types of data structures

**1)Queue - This uses First in First Out mechanism(FIFO)**

**2)Stack - This uses Last in First Out(LIFO) or First In Last Out(FILO)**

__Queue - This uses First in First Out mechanism(FIFO)__

Operations associated with queue are:

**Enqueue:**Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition**Dequeue:**Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition**Front:**Get the front item from queue**Rear:**Get the last item from queue

__Stack - This uses Last in First Out(LIFO) or First In Last Out(FILO)__

A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.

The functions associated with stack are:

**empty()**– Returns whether the stack is empty**size()**– Returns the size of the stack**top()**– Returns a reference to the top most element of the stack**push(g)**– Adds the element ‘g’ at the top of the stack**pop()**– Deletes the top most element of the stack

__Types of Linked Lists__

Singly Linked List

Circular Linked List

Doubly Linked List

__ Singly Linked List__

**Singly Linked Lists** are a type of data structure. ... A **linked list**, in its simplest form, in a collection of nodes that collectively form linear sequence. In a **singly linked list**, each node stores a reference to an object that is an element of the sequence, as well as a reference to the next node of the **list**.

__Circular Linked List__

A **circular linked list** is a sequence of elements in which every element has a **link** to its next element in the sequence and the last element has a **link** to the first element. That means **circular linked list** is similar to the single **linked list** except that the last node points to the first node in the **list**.

**Doubly linked list**

**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**.