Tuesday, February 19, 2019

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.


Posted by at
Labels: , ,
Location: Junagadh, Gujarat, India