Linked List Basics
A linked list is a data structure for storing, searching, manipulating and doing many more with a list of data. ‘Array’ data structure has some limitations that can be overcome easily by the linked list having some dynamic features. Let’s see what a linked list can do –
- Successive elements are connected by pointers.
- Last element points to NULL.
- It can grow or shrink in size during execution of a program.
- It can be made just as long as required.
- It does not waste memory space.
Fig: Liked List Structure
We must know the pointer to the first element of the list (called start, head, etc.).
Insertion and deletion in linked list
- A record is created holding the new item.
- The nextpointer of the new record is set to link it to the item which is to follow it in the list.
- The nextpointer of the item which is to precede it must be modified to point to the new item.
Fig: Linked List Insertion
- The nextpointer of the item immediately preceding the one to be deleted is altered, and made to point to the item following the deleted item.
Fig: Linked List Deletion
Array versus Linked Lists
- Inserting/deleting an element at the end.
- Randomly accessing any element.
- Searching the list for a particular value.
- Inserting an element.
- Deleting an element.
- Applications where sequential access is required.
- In situations where the number of elements cannot be predicted beforehand.
Types of linked lists
Depending on the way in which the links are used to maintain adjacency, several different types of linked lists are possible.
Circular linked list
The pointer from the last element in the list points back to the first element.
Fig: Circular Linked List
Doubly linked list
- Pointers exist between adjacent nodes in both directions.
- The list can be traversed either forward or backward.
- Usually two pointers are maintained to keep track of the list, head and tail.
Fig: Doubly Linked List
Basic Operations on a List
- Creating a list
- Traversing the list
- Inserting an item in the list
- Deleting an item from the list
- Concatenating two lists into one
First of all we need to declare a user defined structure that will carry the information and same type of pointer variable that will lead us to the next address of the element of the list.Let’s declare a node which will hold student info containing roll, name, age of any student and the pointer to the next student of the list.
Initialization of the head node of the list from where we will always start our look up for insertion, deletion and searching any node on any key i.e. name, roll or age –
Allocating memory for the newly created node will be looking like the following-
Or if we want to allocate memory so simply C++ provides the following API. Just we need to assign the name and id.
So our first node is created-
Fig: Head/First node
If there are n number of nodes in the initial linked list:
Allocate n records, one by one.
Read in the fields of the records.
Modify the links of the records so that the chain is formed.
Follow the pointers.
Display the contents of the nodes as they are traversed.
Stop when the nextpointer points to NULL.
Inserting an item in the list
Suppose the problem is to insert a node before a specified node.
- Specified means some value is given for the node (called key).
- In this example, we consider it to be roll.
We have to maintain three different cases here.
Case 1: When a node is added at the beginning-
- Only one next pointer needs to be modified.
- A new node is made the head
- New node points to the previously first element.
Fig: Insert Before Head
Case 2: When a node is added at the end-
- Two next pointers need to be modified.
- Last node now points to a new node.
- New node points to NULL.
Fig: Insert at the end
- Two next pointers need to be modified.
- Previous node now points to the new node.
- New node points to the next node.
Fig: Insert at the middle of two nodes
Let’s see the code snippet for the insertion into the existing list:
Convention: Put it before a key (here we assume roll). If there is no such key put it to the last.
Deleting an item from the list
Here also we are required to delete a specified node. Say, the node whose roll field is given as the key for the deletion. Here also three conditions arise:
Case 1: Delete the node at the beginning
Fig: Delete the first node / head
Case 2: Delete the node at the end
Fig: Delete the last node
Case 3: Delete the node at the middle of two nodes
Fig: Delete node in the middle of two nodes
Let’s see the code snippet which is as simple as the pictures say:
So, these are the basics of the linked list. If you understand these operation, hope you will be able to implement the followings-
- Concatenate two given list into one big list.
- Push, pop operation for Stack and Queue.
- Implement Circular and Doubly linked list.
Comment if anything is unclear to you or point me out if any mistake is sighted. Thanks.