Linked list
A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:
Types of linked lists:
- Singly-linked list
- Doubly linked list
- Circular linked list
- Doubly circular linked list
Characteristics of a Linked list:
A linked list has various characteristics which are as follows:
- A linked list uses extra memory to store links.
- During the initialization of the linked list, there is no need to know the size of the elements.
- Linked lists are used to implement stacks, queues, graphs, etc.
- The first node of the linked list is called the Head.
- The next pointer of the last node always points to NULL.
- In a linked list, insertion and deletion are possible easily.
- Each node of the linked list consists of a pointer/link which is the address of the next node.
- Linked lists can shrink or grow at any point in time easily.
Operations performed on Linked list:
A linked list is a linear data structure where each node contains a value and a reference to the next node. Here are some common operations performed on linked lists:
- Initialization: A linked list can be initialized by creating a head node with a reference to the first node. Each subsequent node contains a value and a reference to the next node.
- Inserting elements: Elements can be inserted at the head, tail, or at a specific position in the linked list.
- Deleting elements: Elements can be deleted from the linked list by updating the reference of the previous node to point to the next node, effectively removing the current node from the list.
- Searching for elements: Linked lists can be searched for a specific element by starting from the head node and following the references to the next nodes until the desired element is found.
- Updating elements: Elements in a linked list can be updated by modifying the value of a specific node.
- Traversing elements: The elements in a linked list can be traversed by starting from the head node and following the references to the next nodes until the end of the list is reached.
- Reversing a linked list: The linked list can be reversed by updating the references of each node so that they point to the previous node instead of the next node.
These are some of the most common operations performed on linked lists. The specific operations and algorithms used may vary based on the requirements of the problem and the programming language used.
Applications of the Linked list:
Different applications of linked lists are as follows:
- Linked lists are used to implement stacks, queues, graphs, etc.
- Linked lists are used to perform arithmetic operations on long integers.
- It is used for the representation of sparse matrices.
- It is used in the linked allocation of files.
- It helps in memory management.
- It is used in the representation of Polynomial Manipulation where each polynomial term represents a node in the linked list.
- Linked lists are used to display image containers. Users can visit past, current, and next images.
- They are used to store the history of the visited page.
- They are used to perform undo operations.
- Linked are used in software development where they indicate the correct syntax of a tag.
- Linked lists are used to display social media feeds.
Real-Life Applications of a Linked list:
- A linked list is used in Round-Robin scheduling to keep track of the turn in multiplayer games.
- It is used in image viewer. The previous and next images are linked, and hence can be accessed by the previous and next buttons.
- In a music playlist, songs are linked to the previous and next songs.
Want to get started with a linked list? You can try out our curated articles and lists for the best practice: