Data Structure : Unit 4 Tree for B.C.A., M.C.A. and all IT Students

--------------------------------------------------------------------------------------------------------------------------
Prepared By : Uday Shah (HOD -IT)
E-Mail : rupareleducation@gmail.com
Contact No : 7600044051

Data Structure  : Unit 4 Tree

Definition and concept of Tree

A tree is a collection of nodes connected by directed or undirected edges. A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

Representation of Binary Tree

In a normal tree, every node can have any number of children. Binary tree is a special type of tree data structure in which every node can have a maximum of 2 children. One is known as left child and the other is known as right child.

A tree in which every node can have a maximum of two children is called as Binary Tree.

In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2 children.

Example

There are different types of binary trees and they are...

1. Strictly Binary Tree

In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node should have exactly two children or none. That means every internal node must have exactly two children. A strictly Binary Tree can be defined as follows...

A binary tree in which every node has either two or zero number of children is called Strictly Binary Tree

Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree

Strictly binary tree data structure is used to represent mathematical expressions.

2. Complete Binary Tree

In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node should have exactly two children or none and in complete binary tree all the nodes must have exactly two children and at every level of complete binary tree there must be 2^level number of nodes. For example at level 2 there must be 2² = 4 nodes and at level 3 there must be 2³ = 8 nodes.

Binary Tree Traversals

When we wanted to display a binary tree, we need to follow some order in which all the nodes of that binary tree must be displayed. In any binary tree displaying order of nodes depends on the traversal method.

Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.

There are three types of binary tree traversals.

1.     In - Order Traversal

2.     Pre - Order Traversal

3.     Post - Order Traversal

Consider the following binary tree...

1. In - Order Traversal ( leftChild - root - rightChild )

In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left child node is visited first, then the root node is visited and later we go for visiting right child node. This in-order traversal is applicable for every root node of all subtrees in the tree. This is performed recursively for all nodes in the tree.

That means here we have visited in the order of B - F - G - H - P - R - S - T - W - Y - Z  using In-Order Traversal.  

2. Pre - Order Traversal ( root - leftChild - rightChild )

In Pre-Order traversal, the root node is visited before left child and right child nodes. In this traversal, the root node is visited first, then its left child and later its right child. This pre-order traversal is applicable for every root node of all subtrees in the tree. 

That means here we have visited in the order of P - F - B - H - G - S - R - Y - T - W - Z using Pre-Order Traversal. 

3. Post - Order Traversal ( leftChild - rightChild - root )

In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left child node is visited first, then its right child and then its root node. This is recursively performed until the right most node is visited.

Here we have visited in the order of  B - G - H - F - R - W - T - Z - Y - S - P using Post-Order Traversal.

Binary Search Tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

·        The left sub-tree of a node has a key less than or equal to its parent node's key.

·        The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST −

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree.

 Application of Trees

·         Represent organization

·         Represent computer file systems

·         Networks to find best path in the Internet

·         Chemical formulas representation

·         Manipulate hierarchical data.

·         Make information easy to search (see tree traversal).

·         Manipulate sorted lists of data.

·         As a workflow for compositing digital images for visual effects.

·         Router algorithms

·         Used in many search applications where data is constantly entering/leaving,

Used in almost every 3D video game to determine what objects need to be rendered.

Graph and its representations

What is Graph? Basic Concept and Definition

·         Graph is an abstract data type.

·         It is a pictorial representation of a set of objects where some pairs of objects are connected by links.

·         Graph is used to implement the undirected graph and directed graph concepts from mathematics.

·         It represents many real life application. Graphs are used to represent the networks. Network includes path in a city, telephone network etc.

·         It is used in social networks like Facebook, LinkedIn etc.

·         Graph consists of two following components:
1. Vertices
2. Edges

·         Graph is a set of vertices (V) and set of edges (E).

·         V is a finite number of vertices also called as nodes.

·         E is a set of ordered pair of vertices representing edges.

·         For example, in Facebook, each person is represented with a vertex or a node. Each node is a structure and contains the information like user id, user name, gender etc.

·         The above figures represent the graphs. The set representation for each of these graphs are as follows:

·         Graph 1:

V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, C), (B, D),(C, E),(D, E), (D, F), (E, F)}

·         Graph 2:

V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, D), (C, E), (C, F)}

Graph 3:

V = {A, B, C}
E = {(A, B), (A, C), (C, B)}

Directed Graph

·         If a graph contains ordered pair of vertices, is said to be a Directed Graph.

·         If an edge is represented using a pair of vertices (V₁, V₂), the edge is said to be directed from V₁ to V₂.

·         The first element of the pair V₁ is called the start vertex and the second element of the pair V₂ is called the end vertex.

  

Set of Vertices V = {1, 2, 3, 4, 5, 5}
Set of Edges W = {(1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}

·        Undirected Graph

·         If a graph contains unordered pair of vertices, is said to be an Undirected Graph.

·         In this graph, pair of vertices represents the same edge.

         

Set of Vertices V = {1, 2, 3, 4, 5}
Set of Edges E = {(1, 2), (1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}

·         In an undirected graph, the nodes are connected by undirected arcs.

·         It is an edge that has no arrow. Both the ends of an undirected arc are equivalent, there is no head or tail.

Graph Traversal

·         Graph traversal is a process of checking or updating each vertex in a graph.

·         It is also known as Graph Search.

·         Graph traversal means visiting each and exactly one node.

·         Tree traversal is a special case of graph traversal.

·         There are two techniques used in graph traversal:

1. Depth First Search
2. Breadth First Search

·        Depth First Search

·         Depth first search (DFS) is used for traversing a finite graph.

·         DFS traverses the depth of any particular path before exploring its breadth.

·         It explores one subtree before returning to the current node and then exploring the other subtree.

·         DFS uses stack instead of queue.

·         It traverses a graph in a depth-ward motion and gets the next vertex to start a search when a dead end occurs in any iteration.

·         DFS does not go though all the edges. The tree contains all the vertices of the graph if it is connected to the nodes and is called as Graph Spanning Tree. Graph spanning tree is exactly corresponds to the recursive calls of DFS.

·         If a graph is disconnected then DFS will not be able to visit all of its vertices.

·         DFS will pop up all the vertices from the stack which do not have adjacent nodes. The process is going on until we find a node that has unvisited adjacent node and if there is no more adjacent node, DFS is over.

·        Breadth First Search

·         Breadth first search is used for traversing a finite graph.

·         It visits the neighbor vertices before visiting the child vertices.

·         BFS uses a queue for search process and gets the next vertex to start a search when a dead end occurs in any iteration.

·         It traverses a graph in a breadth-ward motion.

·         It is used to find the shortest path from one vertex to another.

·         The main purpose of BFS is to traverse the graph as close as possible to the root node.

·         BFS is a different approach for traversing the graph nodes.

Spanning Tree

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected..

By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices.

We found three spanning trees off one complete graph. A complete undirected graph can have maximum  number of spanning trees.

General Properties of Spanning Tree

One graph can have more than one spanning tree. Following are a few properties of the spanning tree connected to graph

·         A connected graph  can have more than one spanning tree.

·         All possible spanning trees of graph, have the same number of edges and vertices.

·         The spanning tree does not have any cycle (loops).

·         Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected.

·         Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic.

Application of Spanning Tree

Spanning tree is basically used to find a minimum path to connect all nodes in a graph. Common application of spanning trees are −

·        Civil Network Planning

·        Computer Network Routing Protocol

·        Cluster Analysis

Let us understand this through a small example. Consider, city network as a huge graph and now plans to deploy telephone lines in such a way that in minimum lines we can connect to all city nodes. This is where the spanning tree comes into picture.

Minimum Spanning Tree (MST)

In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph. In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges.

Shortest-paths is a broadly useful problem-solving model

• Maps

• Robot navigation.

• Texture mapping.

• Typesetting in TeX.

• Urban traffic planning.

• Optimal pipelining of VLSI chip.

• Subroutine in advanced algorithms.

• Telemarketer operator scheduling.

• Routing of telecommunications messages.

• Approximating piecewise linear functions.

• Network routing protocols (OSPF, BGP, RIP).

• Exploiting arbitrage opportunities in currency exchange.

• Optimal truck routing through given traffic congestion pattern.

Following is an Example for Shortest Path.

According to above example here we try to find out shortest way to reach with starting point to ending point.

 There are number of possibility to reached there destination point but we have to find a path that we have to reached fast and safe.

Dijkstra and Greedy Both algorithm try to find a path in shortest way.

Dijkstra algorithm is very small to understand  the path to find the destination.

Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph.

Algorithm

·         Create a set shortest path tree that keeps track of vertices included in shortest path tree.

·         Assign a distance value to all vertices in the input graph.

·         Initialize all distance values as INFINITE.

·         Assign distance value as 0 for the source vertex so that it is picked first.

·         While shortest path tree  doesn’t include all vertices 

·         Pick a vertex v which is not there in shortest path tree and has minimum distance value.

·         Include vertex v to shortest path tree.

·         Update distance value of all adjacent vertices of v.

:: Best Of Luck :: 

https://myshopprime.com/uday.shah3/shop

Please share and comment it... Thank you.

Data Structure Unit : 3 Dynamic Memory Allocation , Link List for B.C.A., P.G.D.C.A. and for All IT Students.

---------------------------------------------------------------------------------------------------------------------
Prepared By : Uday Shah (HOD-IT)
E-Mail : rupareleducation@gmail.com
Contact No : 7600044051

Single Linked List

Dynamic Memory allocation

The concept of dynamic memory allocation in c language enables the C programmer to allocate memory at runtime. Dynamic memory allocation in c language is possible by 4 functions of stdlib.h header file.

1.      malloc()

2.      calloc()

3.      realloc()

4.      free()

malloc() function in C

The malloc() function allocates single block of requested memory.

It doesn't initialize memory at execution time, so it has garbage value initially.

It returns NULL if memory is not sufficient.

calloc() function in C

The calloc() function allocates multiple block of requested memory.

It initially initialize all bytes to zero.

It returns NULL if memory is not sufficient.

realloc() function in C

If memory is not sufficient for malloc() or calloc(), you can reallocate the memory by realloc() function. In short, it changes the memory size.

free() function in C

The memory occupied by malloc() or calloc() functions must be released by calling free() function. Otherwise, it will consume memory until program exit.

What is Linked List?

When we want to work with unknown number of data values, we use a linked list data structure to organize that data. Linked list is a linear data structure that contains sequence of elements such that each element links to its next element in the sequence. Each element in a linked list is called as "Node".

Building a Linked List

TO Build a linklist we just require a simple structure that maintain dynamic concept regarding to create a datastructure. A simple structure that contain two member variable that is Data and link.

following is simple syntax to create or build a linked list.

structure structure_name

{

        data_type variable_name;

        structure_name *Variable_name;
}; 

According to above structure structure name is name of the structure and it has two member variable that is data and link; 

when ever it require new structure using malloc function it allocate memory space and create new link node.

What is Single Linked List?

Simply a list is a sequence of data, and linked list is a sequence of data linked with each other. 

The formal definition of a single linked list is as follows...

Single linked list is a sequence of elements in which every element has link to its next element in the sequence.

In any single linked list, the individual element is called as "Node". Every "Node" contains two fields, data and next. The data field is used to store actual value of that node and next field is used to store the address of the next node in the sequence.

The graphical representation of a node in a single linked list is as follows...

NOTE

☀ In a single linked list, the address of the first node is always stored in a reference node known as "front" (Some times it is also known as "head").
☀ Always next part (reference part) of the last node must be NULL.

Example

Operations

In a single linked list we perform the following operations...

1.      Insertion

2.      Deletion

3.      Display

Before we implement actual operations, first we need to setup empty list. First perform the following steps before implementing actual operations.

• Step 1: Include all the header files which are used in the program.
• Step 2: Declare all the user defined functions.
• Step 3: Define a Node structure with two members data and next
• Step 4: Define a Node pointer 'head' and set it to NULL.
• Step 5: Implement the main method by displaying operations menu and make suitable function calls in the main method to perform user selected operation.

Insertion

In a single linked list, the insertion operation can be performed in three ways. They are as follows...

1.      Inserting At Beginning of the list

2.      Inserting At End of the list

3.      Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the single linked list...

• Step 1: Create a newNode with given value.
• Step 2: Check whether list is Empty (head == NULL)
• Step 3: If it is Empty then, set  newNode→next  =  NULL  and  head  =  newNode.
• Step 4: If it is Not Empty then, set newNode→next  =  head and head =  newNode.

Inserting At End of the list

We can use the following steps to insert a new node at end of the single linked list...

• Step 1: Create a newNode with given value and newNode → next as NULL.
• Step 2: Check whether list is Empty (head == NULL).
• Step 3: If it is Empty then, set head = newNode.
• Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
• Step 5: Keep moving the temp to its next node until it reaches to the last node in the list (until temp → next is equal to NULL).
• Step 6: Set temp → next = newNode.

Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the single linked list...

• Step 1: Create a newNode with given value.
• Step 2: Check whether list is Empty (head == NULL)
• Step 3: If it is Empty then, set newNode → next  =  NULL  and  head  =  newNode.
• Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
• Step 5: Keep moving the temp to its next node until it reaches to the node after which we want to insert the newNode (until temp1 → data is equal to location, here location is the node value after which we want to insert the newNode).
• Step 6: Every time check whether temp is reached to last node or not. If it is reached to last node then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the function. Otherwise move the temp to next node.
• Step 7: Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

Deletion

In a single linked list, the deletion operation can be performed in three ways. They are as follows...

1.      Deleting from Beginning of the list

2.      Deleting from End of the list

3.      Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the single linked list...

• Step 1: Check whether list is Empty (head == NULL)
• Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the function.
• Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
• Step 4: Check whether list is having only one node (temp → next == NULL)
• Step 5: If it is TRUE then set head = NULL and delete temp  (Setting  Empty list conditions)
• Step 6: If it is FALSE then set head = temp → next, and delete temp.

Deleting from End of the list

We can use the following steps to delete a node from end of the single linked list...

• Step 1: Check whether list is Empty (head == NULL)
• Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the function.
• Step 3: If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize 'temp1' with head.
• Step 4: Check whether list has only one Node (temp1 → next == NULL)
• Step 5: If it is TRUE. Then, set head = NULL and delete temp1. And terminate the function. (Setting Empty list condition)
• Step 6: If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node. Repeat the same until it reaches to the last node in the list. (until temp1 → next == NULL)
• Step 7: Finally, Set temp2 → next = NULL and delete temp1.

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the single linked list...

• Step 1: Check whether list is Empty (head == NULL)
• Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the function.
• Step 3: If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize 'temp1' with head.
• Step 4: Keep moving the temp1 until it reaches to the exact node to be deleted or to the last node. And every time set 'temp2 = temp1' before moving the 'temp1' to its next node.
• Step 5: If it is reached to the last node then display 'Given node not found in the list! Deletion not possible!!!'. And terminate the function.
• Step 6: If it is reached to the exact node which we want to delete, then check whether list is having only one node or not
• Step 7: If list has only one node and that is the node to be deleted, then set head = NULL and delete temp1 (free(temp1)).
• Step 8: If list contains multiple nodes, then check whether temp1 is the first node in the list (temp1 == head).
• Step 9: If temp1 is the first node then move the head to the next node (head = head → next) and delete temp1.
• Step 10: If temp1 is not first node then check whether it is last node in the list (temp1 → next == NULL).
• Step 11: If temp1 is last node then set temp2 → next = NULL and delete temp1 (free(temp1)).
• Step 12: If temp1 is not first node and not last node then set temp2 → next = temp1 → next and delete temp1 (free(temp1)).

Displaying a Single Linked List

We can use the following steps to display the elements of a single linked list...

• Step 1: Check whether list is Empty (head == NULL)
• Step 2: If it is Empty then, display 'List is Empty!!!' and terminate the function.
• Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
• Step 4: Keep displaying temp → data with an arrow (--->) until  temp  reaches  to the last node
• Step 5: Finally display temp → data with arrow pointing to NULL (temp → data ---> NULL).

Traversing a Linked List

A linked list is a linear data structure that needs to be traversed starting from the head node until the end of the list.

Unlike arrays, where random access is possible, linked list requires access to its nodes through sequential traversal.

Traversing a linked list is important in many applications. For example, we may want to print a list or search for a specific node in the list.

Or we may want to perform an advanced operation on the list as we traverse the list. The algorithm for traversing a list is fairly trivial.

• Start with the head of the list. Access the content of the head node if it is not null.
• Then go to the next node (if exists) and access the node information
• Continue until no more nodes (that is, you have reached the last node)
• In short Traversal means to travel node from one node to another node. It is also known pointer moving from one node to another node.
• In Entire link list concept Traversal is key point to access all the operation of link list.
• Following is syntax of Traversal.

            node *q = q –> Link;

According to above example node *q is structure node and q->link define the address of next node in a sequence.

Concatenation of two Linked Lists

Let us assume that the two linked lists are referenced by head1 and head2 respectively.

1. If the first linked list is empty then return head2.

2. If the second linked list is empty then return head1.

3. Store the address of the starting node of the first linked
list in a pointer variable, say p.

4. Move the p to the last node of the linked list through simple linked list traversal technique.

5. Store the address of the first node of the second linked
list in the next field of the node pointed by p. Return head1.

Searching of linked lists

·         Searching is the process of finding a given value position in a list of values.

·         It decides whether a search key is present in the data or not.

·         It is the algorithmic process of finding a particular item in a collection of items.

·         It can be done on internal data structure or on external data structure.

·         Write a function that searches a given key ‘x’ in a given singly linked list. The function should return true if x is present in linked list and false otherwise.

·         bool search(Node *head, int x)

·         For example, if the key to be searched is 15 and linked list is 14->21->11->30->10, then function should return false. If key to be searched is 14, then the function should return true.

Following is step to search an element

·         Initialize a node pointer, current = head.

·         Do following while current is not NULL

o   current->key is equal to the key being searched return true.

o   current = current->next

·         Return false 

According to above first need to initialize a node pointer and set current and then check until the element not found in the list if found then display otherwise return false.

Sorting of linked lists

·         Sorting refers to ordering data in an increasing or decreasing fashion according to some linear relationship among the data items.

·          Sorting can be done on names, numbers and records. Sorting reduces the efforts For example, it is relatively easy to look up the phone number of a friend from a telephone dictionary because the names in the phone book have been sorted into alphabetical order.

·         Sorting can use to search data fast.

·         Sorting can use to manage data well.

·         Sorting can use to display data in proper sequence.

·         Sorting can use to store large amount of data.

·         Sorting can use to filter data.

·         Following is step to Sorting an element

·         Initialize a node pointer, current = head.

·         Do following while current is not NULL

·         current->key is Greater Then Next->key being Swapping Data.

·         current = current->next and so on

·         do the process until all the element are not sort in order.

·         Return

According to above first need to initialize a node pointer and set current and then check until the element are not sorted in the list and then return.

Merge two sorted linked lists

Write a SortedMerge() function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. SortedMerge() should return the new list. The new list should be made by splicing together  the nodes of the first two lists.

For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20.

There are many cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally there’s the problem of starting the result list empty, and building it up while going through ‘a’ and ‘b’.

Method 1 (Using Dummy Nodes)

The strategy here uses a temporary dummy node as the start of the result list. The pointer Tail always points to the last node in the result list, so appending new nodes is easy.
The dummy node gives tail something to point to initially when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’, and adding it to tail. When
we are done, the result is in dummy.next.

Method 2 (Using Local References)

This solution is structurally very similar to the above, but it avoids using a dummy node. Instead, it maintains a struct node** pointer, lastPtrRef, that always points to the last pointer of the result list. This solves the same case that the dummy node did — dealing with the result list when it is empty. If you are trying to build up a list at its tail, either the dummy node or the struct node** “reference” strategy can be used

Doubly Linked List

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.

·        Link − Each link of a linked list can store a data called an element.

·        Next − Each link of a linked list contains a link to the next link called Next.

·        Prev − Each link of a linked list contains a link to the previous link called Prev.

·        LinkedList − A Linked List contains the connection link to the first link called First and to the last link called Last.

Following is a diagram to represent Doubly Linked List.

As per the above example, following are the important points to be considered.

·        Doubly Linked List contains a link element called first and last.

·        Each link carries a data field(s) and two link fields called next and prev.

·        Each link is linked with its next link using its next link.

·        Each link is linked with its previous link using its previous link.

·        The last link carries a link as null to mark the end of the list.

Basic Operations

Following are the basic operations supported by a list.

·        Insertion − Adds an element at the end of the list.

·        Delete − Deletes an element from the list using the key.

·                Display  − Displays the complete list in a forward manner.

Inserting At End of the list

We can use the following steps to insert a new node at end of the double linked list...

• Step 1 - Create a newNode with given value and newNode → next as NULL.
• Step 2 - Check whether list is Empty (head == NULL)
• Step 3 - If it is Empty, then assign NULL to newNode → previous and newNode to head.
• Step 4 - If it is not empty, then, define a node pointer temp and initialize with head.
• Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list (until temp → next is equal to NULL).
• Step 6 - Assign newNode to temp → next and temp to newNode → previous.

Deletion

In a double linked list, the deletion operation can be performed in three ways as follows...

1.     Deleting from Beginning of the list

2.     Deleting from End of the list

3.     Deleting a Specific Node

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the double linked list...

• Step 1 - Check whether list is Empty (head == NULL)
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the function.
• Step 3 - If it is not Empty, then define a Node pointer 'temp' and initialize with head.
• Step 4 - Keep moving the temp until it reaches to the exact node to be deleted or to the last node.
• Step 5 - If it is reached to the last node, then display 'Given node not found in the list! Deletion not possible!!!' and terminate the function.
• Step 6 - If it is reached to the exact node which we want to delete, then check whether list is having only one node or not
• Step 7 - If list has only one node and that is the node which is to be deleted then set head to NULL and delete temp (free(temp)).
• Step 8 - If list contains multiple nodes, then check whether temp is the first node in the list (temp == head).
• Step 9 - If temp is the first node, then move the head to the next node (head = head → next), set head of previous to NULL (head → previous = NULL) and delete temp.
• Step 10 - If temp is not the first node, then check whether it is the last node in the list (temp → next == NULL).
• Step 11 - If temp is the last node th set temp of previous of next to NULL (temp → previous → next = NULL) and delete temp(free(temp)).
• Step 12 - If temp is not the first node and not the last node, then set temp of previous of next to temp of next (temp → previous → next = temp → next), temp of next of previous to temp of previous (temp → next → previous = temp → previous) and delete temp(free(temp)).

Displaying a Double Linked List

We can use the following steps to display the elements of a double linked list...

• Step 1 - Check whether list is Empty (head == NULL)
• Step 2 - If it is Empty, then display 'List is Empty!!!' and terminate the function.
• Step 3 - If it is not Empty, then define a Node pointer 'temp' and initialize with head.
• Step 4 - Display 'NULL <--- '.
• Step 5 - Keep displaying temp → data with an arrow (<===>) until temp reaches to the last node
• Step 6 - Finally, display temp → data with arrow pointing to NULL (temp → data ---> NULL).

Advantages over singly linked list

• A Double Link List can be traversed in both forward and backward direction.
• The delete operation in Double Link List is more efficient if pointer to the node to be deleted is given.
• We can quickly insert a new node before a given node.
• In singly linked list, to delete a node, pointer to the previous node is needed. 
• To get this previous node, sometimes the list is traversed. 
• In Double Link List, we can get the previous node using previous pointer.

Disadvantages over singly linked list

• Every node of Double Link List Require extra space for an previous pointer. 
• It is possible to implement Double Link List with single pointer though.
• All operations require an extra pointer previous to be maintained. 
• For example, in insertion, we need to modify previous pointers together with next pointers. 
• For example functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.

Stack Using Linked List

·     The major problem with the stack implemented using array is, it works only for fixed number of data values.

·   That means the amount of data must be specified at the beginning of the implementation itself.

·     Stack implemented using array is not suitable, when we don't know the size of data which we are going to use.

·     A stack data structure can be implemented by using linked list data structure. The stack implemented using linked list can work for unlimited number of values.

·     That means, stack implemented using linked list works for variable size of data. So, there is no need to fix the size at the beginning of the implementation.

·       The Stack implemented using linked list can organize as many data values as we want. 

In linked list implementation of a stack, every new element is inserted as 'top' element. That means every newly inserted element is pointed by 'top'. Whenever we want to remove an element from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its previous node in the list. The next field of the first element must be always NULL.

Following is an example of Stack with Linked List.

In above example, the last inserted node is 99 and the first inserted node is 25. The order of elements inserted is 25, 32,50 and 99.

Stack Operations using Linked List

To implement stack using linked list, we need to set the following things before implementing actual operations.

• Step 1 - Include all the header files which are used in the program. And declare all the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define a Node pointer 'top' and set it to NULL.
• Step 4 - Implement the main method by displaying Menu with list of operations and make suitable function calls in the main method.

Inserting an element into the Stack

We can use the following steps to insert a new node into the stack...

• Step 1 - Create a newNode with given value.
• Step 2 - Check whether stack is Empty (top == NULL)
• Step 3 - If it is Empty, then set newNode → next = NULL.
• Step 4 - If it is Not Empty, then set newNode → next = top.
• Step 5 - Finally, set top = newNode.

Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).

Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
• Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until temp reaches to the first node in the stack. (temp → next != NULL).
• Step 5 - Finally! Display 'temp → data ---> NULL'.

Queue Using Linked List

·        The major problem with the queue implemented using array is, It will work for only fixed number of data values.

·        That means, the amount of data must be specified in the beginning itself.

·        Queue using array is not suitable when we don't know the size of data which we are going to use.

·        A queue data structure can be implemented using linked list data structure.

·        The queue which is implemented using linked list can work for unlimited number of values.

·        That means, queue using linked list can work for variable size of data (No need to fix the size at beginning of the implementation).

·        The Queue implemented using linked list can organize as many data values as we want.

In linked list implementation of a queue, the last inserted node is always pointed by 'rear' and the first node is always pointed by 'front'.

     Following is an Example of Queue with Link List.

In above example, the last inserted node is 50 and it is pointed by 'rear' and the first inserted node is 10 and it is pointed by 'front'. The order of elements inserted is 10, 15, 22 and 50.

Operations

To implement queue using linked list, we need to set the following things before implementing actual operations.

• Step 1 - Include all the header files which are used in the program. And declare all the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
• Step 4 - Implement the main method by displaying Menu of list of operations and make suitable function calls in the main method to perform user selected operation.

Inserting an element into the Queue

We can use the following steps to insert a new node into the queue...

• Step 1 - Create a newNode with given value and set 'newNode → next' to NULL.
• Step 2 - Check whether queue is Empty (rear == NULL)
• Step 3 - If it is Empty then, set front = newNode and rear = newNode.
• Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode.

Deleting an Element from Queue

We can use the following steps to delete a node from the queue...

• Step 1 - Check whether queue is Empty (front == NULL).
• Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function
• Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.
• Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).

Displaying the elements of Queue

We can use the following steps to display the elements (nodes) of a queue...

• Step 1 - Check whether queue is Empty (front == NULL).
• Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
• Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with front.
• Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp' reaches to 'rear' (temp → next != NULL).
• Step 5 - Finally! Display 'temp → data ---> NULL'.

Applications of Linked List data structure

• Linked Lists can be used to implement Stacks , Queues.
• Linked Lists can also be used to implement Graphs. (Adjacency list representation of Graph).
• Implementing Hash Tables  :   Each Bucket of the hash table can itself be a linked list. (Open chain hashing).
• Undo functionality in Photoshop or Word . Linked list of states.
• A polynomial can be represented in an array or in a linked list by simply storing the coefficient and exponent of each term.
• However, for any polynomial operation , such as addition or multiplication of polynomials , linked list representation is more easier to deal with.
• Linked lists are useful for dynamic memory allocation.
• The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running.

:: Best Of Luck ::

Please share and comment it... Thank you.