Linked list is a ADT(Abstract Data Type) consisting of group of nodes in a connected way forming a sequence. A linked list is used to maintain dynamic series of data. Each node of a linked list basically contains only two parts data part and the address part. Data part of the node hold the actual data while the address part of the node holds the reference or address to its next connected node. Linked list got its name because here each list (node) is linked to another list (node).
Here in the picture you can see that a linked list is composed mainly of nodes and each node contains the address of its next connected node.
What is a Node?
A node is the main structure of the linked list. It contains all details about the data and the address of next node. A node can contain many data fields and many address fields, but should contain at least one address field. Address part of last node contains a NULL value specifying end of the list. In computer programming a node can be represented either by structures (struct in C or C++) or by classes (class in C++ or Java) and address part of a node is basically represented by pointers (in C and C++). Here is a basic structure of a node in C programming language.
/*
* Basic structure of a node
*/
struct node {
int data; // Data
struct node * next; // Address
};Advantages of linked list
- Linked list provides dynamic allocation of memory, which allocates memory as per need during the execution of a program.
- It is one of the simplest data structure to implement.
- Insertion and deletion of data from the list is easy.
Disadvantages of linked list
- In order to access any element of a linked list the user has to access it in a sequential manner form the start of the list.
- Linked list generally occupy more memory than arrays due to extra storage space for address fields.
- Since elements of a linked list are not stored in a contiguous way hence accessing time of each element is slightly greater.