Introduction to Linked Lists
Linked List is a linear data structure whose elements are linked together by links. These links are connected in a sequence and each link carries its own data and the address to the next link thus forming a chain.
As evident by the diagram above, the Linked list has:
- A link element called first.
- Each link has its own data item and the address to the next link.
- The last link of the list is null
Applications of Linked Lists
- Linked lists are used to implement stack, queue or graphs.
- Linked Lists are used to insert elements at the beginning or the end of the list.
- We don’t need to worry about the size of the list in the linked lists.
Advantages of Linked Lists
- Insertion and deletion operations can be easily carried out.
- It reduces access time.
- Easily implements stacks and queues.
Disadvantages of Linked Lists
- Pointers need extra memory for storage thus memory gets wasted.
- Random access to the elements is not possible. The sequential approach has to be followed.
- Reverse Traversing is difficult.
Types of Linked Lists
There are three major types of Linked Lists. Lets discuss each in detail.
Singly Linked List
Singly linked list as the name suggests contains the nodes with data and the next part. Next part contains the address to the next node in the sequence.
Doubly Linked List
In the doubly linked list, the node contains data along with the next and previous part. The next part contains an address to the next node in the sequence and the previous part contains the address to the node before.
Circular Linked List
In a circular linked list, the last node of the list holds the address of the first node and hence forms a complete circle.