Data Structures in C Language

Data Structures in C Language Part 2

Linked Lists:

A linked list can be viewed as a group of items, each of which points to the item in its neighbourhood. An item in a linked list is known as a node. A node contains a data part and one or two pointer part which contains the address of the neighbouring nodes in the list.

A linked list is called so because each of items in the list is a part of a structure, which is linked to the structure containing the next item. This type of list is called a linked list since it can be considered as a list whose order is given by links from one item to the next. Linked list is a data structure that supports dynamic memory allocation and hence it solves the problems of using an array.

Advantages of Linked Lists:

A linked list is a dynamic data structure and therefore the size of the linked list can grow or shrink in size during execution of the program. A linked list does not require any extra space therefore it does not waste extra memory. It provides flexibility in rearranging the items efficiently.

The limitation of linked list is that it consumes extra space when compared to a array since each node must also contain the address of the next item in the list to search for a single item in a linked list is cumbersome and time consuming process.

Types of Linked Lists: The different types of linked lists are

•    Singly linked lists
•    Circular linked lists
•    Doubly linked lists

Simple/Singly Linked Lists:

In singly linked lists, each node contains a data part and an address part. The address part of the node points to the next node in the list.

Each node is divided in two parts.
•    data field.
•    pointer.

For Example:

Node structure
     Data           field           Pointer field
        
The data field contains the data elements that have to be stored in the list. The pointer will point the next node in the list.
Possible Operations on a singly linked list are

•    Insertion
•    Deletion

Insertion: Elements are added at any position in a linked list by linking nodes.

Deletion: Elements are deleted at any position in a linked list by altering the links of the adjacent nodes.

Insertion:

Insertion in the head node: To insert a node in the head node, just change the pointer field of the new node to point to the head node. Let the new node be ‘Temp’ and the head node be ‘Head’, then the insertion is

Temp? data = X;
Head? next = head

 Insertion in the middle node: To insert in the middle node we need to change two pointers. Let the new node be ‘Temp’ and the present node is ‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is

Temp? data = X

Present? next = temp
Temp? next = future

Insertion in the last node: To insert an element in the last position just change the pointer field of the present last node to point to the new node, then set the pointer field of the new node to NULL. Let the new node be ‘Temp’ and the present node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Present? next =Temp
Temp? next =null
Temp? data = X 

Deletion:

Deletion in the head node: To delete a node in the head node, just point the head node as the second node. Let the head node be ‘Head’, and then the deletion is
Head? next = head

Deletion in the middle node: To delete a node in the middle we need to change two pointers. Let the node to be deleted is ‘Temp’ and the node previous to the node to be deleted is ‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the  data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Present? next = future

Deletion in the last node: To delete an element in the last position just change the pointer field of the previous node to the last to null. Let the last node be ‘Temp’ and the previous node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Previous? next =NULL 

Implementation of a singly linked list:

Creating a linked list: A node in a linked list is usually a structure in C and can be declared as
struct Node
{
int info;
Node *next;
}; //end struct
A node is dynamically allocated as follows:
Node *p;
p = new Node;
For creating the list, the following code can be used:
do
{
Current_node = malloc (sizeof (node));
Current_node->info=input_value;
Current_node->next=NULL;
if(root_node==NULL) // the first node in the list
root_node=Current_node;
else
previous_node->next=Current_node;
previous_node=Current_node;
scanf ("%d", &input_value);
} while(x! =-999);

The above given code will create the list by taking values until the user inputs -999.

Inserting an element: After getting the position and element which needs to be inserted, the following code can be used to insert an element to the list

if (position==1||root_node==NULL)
{
Current_node->next=root_node;
Root_node=Current_node;
}
else
{
counter=2;
temp_node=root_node;
while ((counter<position) && (temp_node!=NULL))
{
counter++;
temp_node=temp_node->next;
}
Current_node->next=temp_node->next;
temp_node->next=Current_node;
}  

Deleting an element: After getting the element to be removed, the following code can be used to remove the particular element.
temp_node=root_node;
if (root_node != NULL )
if (temp_node->info == input_element )
{
root_node=root_node->next;
return;
}
while (temp_node != NULL && temp_node->next->info !=
input_element)
temp_node = temp_node->next;
if (temp->next != NULL )
{
delete_node = temp_node->next;
temp_node->next=delete_node->next;
free (delete_node );
}

Circular linked lists:

In a circularly-linked list, the first and final nodes are linked together. In another words, circularly linked lists can be seen as having no beginning or end. To traverse a circular linked list, begin at any node and follow the list in either direction until you return to the original node.

This type of list is most useful in cases where you have one object in a list and wish to see all other objects in the list. The pointer pointing to the whole list is usually called the end pointer. The advantage of using Circular Linked List is the last null pointer is replaced and the pointer field of the last node points to the first node, due to this circular arrangement the traversing become quite easier. The insertion and deletion in the first and middle are same as singly linked list except the last node.

Insertion:

Insertion in the last node: To insert a node in the last position, insert the new node after the current last node, and then change the pointer field of the new node to point to the first node. Let the last node be last, the new node to be inserted to be new, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Last? next = new
New? next =first

Deletion:

Deletion in the last node: To delete a node in the last position, change the pointer field of the previous node to the current last to point the first node. Let the last node be last, the previous node to the current last node to be pre, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the deletion is
Prev? next = first
Singly-circularly-linked list:  In a singly-circularly-linked list, each node has one link, similar to an ordinary singly-linked list, except that the link of the last node points back to the first node. As in a singly-linked list, new nodes can only be efficiently inserted after a node we already have a reference to.
For this reason, it's usual to retain a reference to only the last element in a singly-circularly-linked list, as this allows quick insertion at the beginning, and also allows access to the first node through the last node's next pointer.
Doubly-circularly-linked list: In a doubly-circularly-linked list, each node has two links, similar to a doubly-linked list, except that the previous link of the first node points to the last node and the next link of the last node points to the first node. As in doubly-linked lists, insertions and removals can be done at any point with access to any nearby node. 

 Doubly-linked list:

A more sophisticated kind of linked list is a doubly-linked list or a two-way linked list. In a doubly linked list, each node has two links: one pointing to the previous node and one pointing to the next node.               
 Implementation of a doubly linked list:
Adding an element to the list
To add the first node
first_node->next = NULL;
first_node->data = input_element;
first_node->prev = NULL;
To add a node at the position specified
Temp_node = *first_node;
for ( counter = 0 ; counter<position-1 ; counter++ )
{
Temp_node = Temp_node->next;
}
new_node->next = temp_node->next;
temp_node->next->new_node;
new_node->prev = temp_node->next->prev;
temp_node->next->prev = new_node;
Deleting a particular element from the list
Temp_node = *first_node;
If (temp_node->data = = input_element)
First_node = first_node->next;
else
{
while ( temp_node != NULL && temp_node->next->data !=input_element)
temp_node = temp_node -> next;
delete_node=temp_node->next;
temp_node->next=delete_node->next;
delete_node->next->prev=temp_node;
free (delete_node);
}

0 comments:

Post a Comment