Link-list
These nodes consist of the data to be stored and a pointer to the address of the next node within the linked list. In the case of arrays, the size is limited to the definition, but in linked lists, there is no defined size. Any amount of data can be stored in it and can be deleted from it.
Types of Link-list
➤Singly Linked List:
Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.
➤Doubly Linked Lists:
Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.
➤Circular Linked Lists
Circular linked lists can exist in both singly linked list and doubly linked list. Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.
Basic Operations in the Linked Lists
The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an element at a given key. These operations are performed on Singly Linked Lists as given below −
➤Insertion Operation:
Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted
step:1. START
step:2. Create a node to store the data
step:3. Check if the list is empty
step:4. If the list is empty, add the data to the node and assign the head pointer to it.
step:5. If the list is not empty, add the data to a node and link to the current head. Assign the head to the newly added node.
step:6. END
➤Deletion Operation:
Deletion in a linked list involves removing a node from the list. The process typically consists of updating the pointers of the surrounding nodes to bypass the node being deleted.
Point head to the next node i.e. second node
temp = head
head = head->next
Make sure to free unused memory
free(temp); or delete temp;
➤Traversal Operation:
The idea here is to step through the list from beginning to end. For example , we may want to print the list or search for a specific node in the list.
STEP 1: SET PTR = HEAD
STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 7
END OF IF
STEP 4: REPEAT STEP 5 AND 6 UNTIL PTR != NULL
STEP 5: PRINT PTR→ DATA
STEP 6: PTR = PTR → NEXT
STEP 7: EXIT
step:2. Create a node to store the data
step:3. Check if the list is empty
step:4. If the list is empty, add the data to the node and assign the head pointer to it.
step:5. If the list is not empty, add the data to a node and link to the current head. Assign the head to the newly added node.
step:6. END
Point head to the next node i.e. second node
temp = head
head = head->next
Make sure to free unused memory
free(temp); or delete temp;
temp = head
head = head->next
Make sure to free unused memory
free(temp); or delete temp;
➤Traversal Operation:
The idea here is to step through the list from beginning to end. For example , we may want to print the list or search for a specific node in the list.
STEP 1: SET PTR = HEAD
STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 7
END OF IF
STEP 4: REPEAT STEP 5 AND 6 UNTIL PTR != NULL
STEP 5: PRINT PTR→ DATA
STEP 6: PTR = PTR → NEXT
STEP 7: EXIT
STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 7
END OF IF
STEP 4: REPEAT STEP 5 AND 6 UNTIL PTR != NULL
STEP 5: PRINT PTR→ DATA
STEP 6: PTR = PTR → NEXT
STEP 7: EXIT