Linked List definition
List or linked list is a collection of nodes/recodes linked with each other using pointer. A node data structure has at least a member to hold the current element value and a pointer to point to the next node.
Linked List data-structure
In this example nodes will be object of structure slist_node. Node_value member will be used to hold a user value. Member “next” will be used to point the next member in the list.
The first node of the linked list is called head and last node is the tail. When there is no element both head = tail = null. A new node object is created from heap using malloc/new and added to the list by setting proper value of the next/previous pointer. When we need to delete a particular node, we modify the next/previous pointer of the neighboring node and delete the node from heap using free/delete. This is a vital advantage list over array. We can add or remove any node at any location and memory is allocated or de-allocated at the run time.
Allocate New node
new_node() function allocates new node for the given input value. It also takes care memory allocation error.
Add at head
add_head() function allocates and adds a node before the existing head. New allocated node becomes the new head for the list.
Add at end/tail
add_tail() function allocates and adds a node after the tail. New allocated node becomes the new head for the list.
Delete head
delete_head() function deletes head and returns the new head which is the node next to the head.
Delete tail
delete_tail() function deletes tail and makes the previous node as tail. If head is the only node in the list then list becomes empty.
Advantages
- Best utilization of memory at run time.
- Addition and removal of any element is at any position is possible. Thus it eliminates constrain of the array where we cannot add or remove elements after the whole array has been allocated once.
Disadvantages
- It uses some few bytes(pointer 4 byte for 32 bit) extra for each element.
- Finding any element is not straight forward as array. It needs iteration and more CPU cycle.
Types of Linked lists
There are four types of list used in common programming practices. They are -
- Single Linked List: Each node has only next pointer to point the next node in the list.
- Doubly Linked List: Each node has both next and previous pointer to point next and previous node in the list.
- Circular Linked List: Next pointer of tail node points to again head node.
- Doubly Circular Linked List: This list has both the properties of doubly linked list and circular linked list.
About our authors: Team EQA
You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.