Data Structure : Linked List, Stack and queues
Creating and Managing Linked Lists
————————————————–
List generally refers to a sequential organization of items like an array.
Array allocates memory of size, which we determine in the beginning itself. Later this can be used for storing values.
A linked list is a chain of structures in memory. These structures contain data as well as a pointer to the next logical structure in the list
struct list {
datatype data;
………
………
struct list *next;
/* next is a pointer of type struct list, pointing to the next logical structure in the list */
};
Advantages of Linked Lists
———————————————–
Linked lists have several advantages over arrays-
One does not have to decide on the number of items in the linked list.
This is because memory can be allocated dynamically as and when a node is added to the list.
Types of Linked Lists
————————————
There are several types of linked lists, two of which will be discussed in this chapter –
Singly Linked List – each node contains the address of the next node in the list. The start node points to the first node in the list.
Doubly Linked List – each node contains the address of the next node as well as the previous node in the list. The start node points to the first node in the list whereas the end node points to the last node.
Singly Linked Lists
——————————-
The operations that can be performed on singly linked lists are listed below –
Creation of a list
Insertion of nodes
Traversal of the list
Search of a specific node
Modification of a node
Deletion of a node
Insertion in a list
——————————–
Assuming that a node has to be inserted at the beginning of an existing linked list, the following steps has to be performed :
Initialize, allocate memory and accept data into a node, let this node be called new.
Make new’s next point to what start is pointing to, i.e., the first node in the list. This can be done by new->next = start;
Make start point to new (i.e., make it the first node). This can be done by start=new;
Creation of a Singly Linked List
———————————————
This involves two steps :
Creating a new node (allocate memory for the node and accept data into it).
Storing the address of the node created in start. start=new;
Traversing a Linked List
———————————
This involves the following steps:
Set list_ptr to start (assume that list_ptr is a pointer declared of type struct list).
Print the information part of the node.
Advance the pointer so that it points to the next node. This can be done by list_ptr=list_ptr->next;
Repeat steps 2 and 3 until list_ptr is equal to NULL.
list_ptr=start;
while(list_ptr)
{
printf(“ %c”, list_ptr->information);
list_ptr=list_ptr->next;
}
Searching in a Linked List
—————————————-
Linked lists can be of two types –
Sorted
Unsorted
Searching in a linked list involves traversing the list until the required node is reached.
Modification in a linked list involves –
Searching for the node to be modified.
Changing the information part of the node.
Deletion in a Singly Linked List
———————————————-
For deleting a node at the beginning of a list, the steps involved are –
Set ptr to start.
Set start to point to what ptr’s next is pointing to start=ptr->next;
Free the memory occupied by the node free(ptr);
Doubly Linked Lists
————————————
A Doubly Linked List is just an extension of the concept of a singly linked list. Each node in a doubly linked list has an information part and two pointers – one pointing to the next node and one to the previous node.
Representing Doubly Linked Lists in C
Doubly Linked Lists are represented in C in the same manner in which singly linked lists are.
struct dlist {
datatype data;
………
………
struct dlist *next;
struct dlist *prior;
};
Traversal in a Doubly Linked List
————————————————–
Traversal in a doubly linked list can be done in two directions –
Start from the beginning of the list to the end of the list.
Start from the last node and traverse in the opposite direction to the first node.
Circular Linked Lists
—————————————
A circular linked list is obtained by modifying the link of the last node in a linked list.
The main drawback of circular lists is that a node can be accessed from a given node by traversing through the list.
Implementing Stacks
————————————
A Stack is a data structure in which insertions and deletions are restricted to one end called Top.
Stacks are also called Last-In-First-Out (LIFO) lists because they come out in the reverse order in which they go in
