Types of Linked List
Before knowing about the types of a linked list, we should know what is linked list. So, to know about the linked list, click on the link given below:
Difference between Singly linked list and Doubly linked list
Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Basically the ‘link’ field stores the address of the next node.
Introduction to Doubly linked list : A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
Singly linked list vs Doubly linked list
| SLL nodes contains 2 field -data field and next link field. | DLL nodes contains 3 fields -data field, a previous link field and a next link field. | |
| In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only. | In DLL, the traversal can be done using the previous node link or the next node link. Thus traversal is possible in both directions (forward and backward). | |
| The SLL occupies less memory than DLL as it has only 2 fields. | The DLL occupies more memory than SLL as it has 3 fields. | |
| Complexity of insertion and deletion at a given position is O(n). | Complexity of insertion and deletion at a given position is O(1). |
What is difference between SLL and DLL?
SLL has nodes with only a data field and next link field. DLL has nodes with a data field, a previous link field and a next link field. In DLL, the traversal can be done using the previous node link or the next node link. The SLL occupies less memory than DLL as it has only 2 fields.
What is the advantage of double linked list over single linked list?
Following are advantages/disadvantages of doubly linked list over singly linked list. 1) A DLL can be traversed in both forward and backward direction. 2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given. 3) We can quickly insert a new node before a given node.
What are Linked Lists?
Linked Lists are a type of data storage, in other words, it simply stores and organizes your data. This data can be almost anything, from integers to strings, and even objects.
Generally, the structure consists of Nodes that contain data and an address (or addresses) to other Nodes. This allows you to traverse (or navigate) between the nodes, in order to achieve some goal, or just add a browsing system. You can think of this Node system as a train that has different carts that are all connected.
Types of Linked List - Singly linked, doubly linked and circular
In this tutorial, you will learn different types of linked list. Also, you will find implementation of linked list in C.
Before you learn about the type of the linked list, make sure you know about the LinkedList Data Structure.
There are three common types of Linked List.
- Singly Linked List
- Doubly Linked List
- Circular Linked List