Summary
| Data Structure Name | Linked List |
| Type | Linear Data Structure |
| Tagline | |
| Use cases | |
| Types | Singly Linked List Doubly Linked List Circular Linked List Circular Doubly Linked List |
Definition
Linked list is a collection of sequential data elements, each element linking to the next (and previous for certain types) element. The size of a linked list is not fixed, it changes as items are added or removed from the list.
A linked list is a data structure, that can store any data type. Data is stored in a linear order, and we can only traverse through the list and then select some items.
Types
Linked list can be of the following types, depending on the type of implementation-
Use Cases
When we have a long data list, and we don’t need random access to an element, then we should use a linked list.
NOTE
Advantages of using a Linked List over an array is-
Insertion and deletion of an element in a list is less expensive than an array.
If we insert or delete an element in an array, then we have to shift the elements from that position. Everything after the insert/delete position needs to be reindexed.
But in a list, we add and/or delete the item by just changing the pointers of a node.
But the issue with Linked List is-
Every time we want access an element either by index or we try to search some data, we have to start from the head, and traverse throught the elements until we reach our desired node.
While, in an array we can access the element by index directly.
Characteristics
Elements
A Linked List data structure has the following info-
- Head
- Tail
- Length
Each element in a linked list is called a node. So a Linked List is just a collection of nodes.
Each node has the following info-
- value: the value(of any kind) that we want to store. Can be a string, number, object, etc. anything supported by the implemented programming language.
- Pointer: information of the next or previous node.
- A singly linked list has 1 pointer for the next node reference.
- A doubly linked list has 2 pointers-
- 1 for the next node,
- 1 for the previous node.
NOTES
- Random/direct access to an element is not allowed in a list. Nodes do not have any index (like an array), so the elements can not be accessed directly using any index. We have to traverse from the first node, to go to any desired node.
- In a singly linked list, the last element(tail) has null as the pointer of the next node, as there is no next node after that.
- In a doubly linked list-
- The first element(head) has null as the previous node pointer, as this is no node before that.
- the last element(tail) has null as the next node pointer, as there is no node after that.
Functionality
