The fondest memories of a child are the different birthday parties and the games/activities during that day. As a child on my birthday, I was introduced to a type of scavenger hunt where an initial clue was given to you. As you solved each clue, you found a gift and a clue to the next gift. This went on till the final gift was found at which point no further clues were provided.
An array is not a right structure to use for this type of data storage as the location of each clue and gift is different. Also, if you would like to add in more clues/gifts, an array would not be a good choice as arrays have fixed length.
A linked list would be a better method for this type of data storage. It contains an element to store the data and a link (clue) to the next data item. Basic parts of a node in a linked list are shown below
What is a linked list?
A Linked List is a data structure used for storing collections of data. Each element is connected to the next using pointers and the last element points to a null (not always but take my word for it now).
A simple representation of a linked list
Implementation of linked lists
Linked lists can be used to implement several other common abstract data types including lists, stacks, queues, etc
Inserting an item in the list at start position
- Create a new node and update the next pointer of the node to point to the current head
- Update head pointer to the new node
Inserting an item in the list at end position
- Create a new node and point the next pointer to NULL
- Traverse the list till you reach the end and point the last nodes next pointer to the new node
Inserting an item in the list at middle(different) position
- Traverse to the position that you want to insert the new node. Point the next pointer of the new node to the position following your current position.
- Now point the position node’s next to the new node.
Deleting an item in the list at start position
- Create a temporary node to point to the same node as head
- Move head to the next node and delete the temporary node
Deleting an item in the list at end position
- Traverse the linked list (curr)and maintain the node of the previous pointer (prev).
- Update prev node link to NULL and delete the last pointer (curr).
Deleting an item in the list at middle(different) position
- Traverse to the position that you want to delete the new node and maintain node to be deleted and previous nodes.
- Update the next pointer for the prev node to the next pointer of the node to be deleted and delete the node
Traversing the list
To traverse a list, you print the value of each node and move to the next pointer. Repeat this till you reach to the end of the linked list.
How is it different from an array?
- Arrays have fixed lengths, Linked lists can be grown or shrunk as long as space is available.
- For a linked list, insertion/deletion at the beginning of a list is independent of the number of elements in it. it is a constant time operation (O(1)). For an array, it is dependent on the number of elements in the array. The amount of time it take is dependent on the number of elements in the array (O(n)).
- For a linked list, insertion/deletion at the end of a list is dependent of the number of elements in it. The amount of time it take is dependent on the number of elements in the array (O(n)). For an array, it is a O(1) operation.
In this blog post, we understood the basics of linked list including inserting, deleting and traversing. In the next blog post, let us dive deeper into doubly linked list and circular linked lists