Linked list is the most basic form of a data structure. A linked list is more or less similar to an array in that it can hold a list of values. But the similarity ceases here. The major difference between a linked list and array is that an array can hold values belonging to the same data type only whereas there is no such restriction on a linked list. For example, if an array is declared with type as int in C language, it can hold only integer values. Coming to a linked list, as it is a data structure, there is seldom any type associated with it.
Apart from the above difference, there is one more difference that makes linked lists more versatile. It is not only possible to create linear linked lists but also circular linked lists i.e., the last element of the list can be made to point to the first. Another difference is that the memory to be allocated to a linked list can be specified dynamically i.e., we need not mention the number of elements in the linked list at the time of compilation. This facility may also be available for arrays in some languages but is not widely used.
The most basic form of a linked list is created by creating a structure with one data element and a pointer to point to the next element in the data structure. The pointer of the last element is intialised to null to avoid it to point to some junk value if its a linear linked list. On the contrary, if it is a circular linked list, the pointer of the last element is made to point to the first element in the list.
The above type of list allows traversing in only one direction. If we want bi-directional traversal, then we can create a structure with two pointers where one pointer is made to point to the previous element and the other point to the next element in the list. PREV of the first node of doubly linked list always points to NULL and also the NEXT of last node points to NULL. Modifications are made as stated above for a simple linked list to convert this to a circular list. Accordingly the above two types of lists are sometimes called single linked list and double linked list.
Instead of using a single data element, we can use any number of data elements with several different data types within the structure. We may also use arrays as data elements of the linked list. An element in a linked list is often called a node. It is possible to add/delete nodes from any position within the linked list. According to the operation selected, the pointers need to be updated appropriately.
The different operations that can be performed on list are:
INSERT:- We can dynamically insert any node at any desired position into the list.
DELETE:- Similar to insertion, deletion can also be accomplished dynamically.
TRAVERSE:- Traversing is just travelling through the list visiting each node.
As each thing has pros and cons, the only drawback of linked list is randomly accessing of element which can be achieved through array index in array but not in linked list.The good thing about linked list is its runtime expandability which proves its flexibility.
Linked List is a Data storage mechanism in which list of data is stored in linear order. Linked list contains collection of nodes, each node contains data part and address part in which the next node address is stored.
Each element in the list is known as Node.
And each node in the have at least two parts:-
1. Data Part
2. Link part
Data Part:- This part of every node of the list contains the information stored in that node of the list
Link Part:- This part of the node contains the memory address of the next node in the linked list.
For Example:Implementation of linked list node in C Language
Struct Node
{
int RollNo;//Data Part
int Marks;//Data Part
struct Node *link;//Address of the next Node
};
Note that the linked list contains a special node called the START which contains the address of the first node in the linked list.
if START == NULL //then it means that the linked list is Empty.
the last node of the list contains NULL in its link part which marks the end of the list.
Each node in link list contains address of next node except the last node because last node contains the NULL pointer which indicates the end of list.
Link list data structure is created using the Structure of C as given below:
struct list
{
int data;
struct list *next;
};
The dynamic node is created using malloc() and calloc() functions available in C language and new operator is used in case of C++.
The following Operation can be performed on link list:
1.Insert element
2.Delete Element
3.Find Sum of All elements
4.Count number of node in list
5.Search any element
6.Reverse the list
7.Make copy of list
8.Merger two list
9.Update element
Link list is widely used by various real life applications. Linked list can be implemented in various applications such as Relational Database System and many other field.
Blog Author: Vijay Kumar |
No comments:
Post a Comment