TwitterA linked list is a data structure which consists of elements linked together as a chain. The advantage of a linked list is that the dynamic insertion and deletion of elements is faster than using a conventional grouping such as an array. The disadvantage is that to access an element we have to follow a sequential path from the head of the list.
A linked list is created by having what is called a self referential structure to create a node of the linked list as shown:
typedef struct ListNode_
{
void* data;
struct ListNode_* next;
}ListNode;
As can be seen, the next is a pointer to the same structure. So by using this next to point to another element, we can create a chain as shown.
A singly linked list
The start node is called the head and the end node is called the tail.
There are three types of linked lists: singly, doubly and circular. In a singly linked list, one element points to the next so traversal is sequential from one element to the next. We cannot traverse back from one element to the previous. In a doubly linked list, the element points to the next as well as the previous. So we can traverse in both directions. In a circular linked list, the tail element points to the head. So we can traverse in a circular fashion. Circular linked lists can be singly or doubly linked.
A doubly linked list
A circular linked list
I have written a basic singly linked list implementation in C. The compiler used was GCC 4.4.1 on a Ubuntu Linux machine. This is a singly linked list with provision for entering any type of data into the list. Elements can be inserted or deleted from the list. To search the list, we will have to create our own searching mechanism depending on the comparison of the data entered in the list.
There is also a program to understand the usage of the insertion and deletions in the linked list. Please note that the program has been lightly tested.
Download the implementation of a singly linked list
Related Posts:
Tags: programs
Frank Silbermann (2)
Abhishek (1)
Asim (1)
Igor Popov (1)
ManiKanta (1)