Linked List
Linked Lists
- Linked List is the basic data structure used in computer science
- They are the foundation for more complex data structures.
- A linked list is a fundamentally different way of storing elements.
- In a linked list, each element stores the reference to the element after it.
- The image represent below is a linked list:
- Here, Head corresponds to the first node in the linked list and each is connected to the other via reference till the last node points to null or None.
Adding and removing from the Linked List
- As nodes in the linked list is linked to only one node, we can't directly just add or remove without maintaining the surrounding nodes as it would mess up the list.
- Adding the new Node
- In order to add a new node at the beginning requires you to link your new node to the head of the list. And then update the head of the linked list to the new node.
- Removing the node
- If you directly remove a node from the middle of the list without altering the side nodes will leave you with some orphaned nodes.
- When removing a node from the middle of a linked list, you must make sure to adjust the link on the previous node so that it points to the following node.
- Here is the image for your better understanding:
- In order to remove the node with data 14, we first change the head refers to the next node of a node with 14 data, leaving the node orphaned and listing the remaining contact.
Review
Lists that are linked:
- Is made up of nodes
- Each node has a link to the next node (and also the previous node for bidirectionally linked lists i.e. Doubly Linked List).
- It is possible for it to be unidirectional or bidirectional.
- Are a fundamental data structure that serves as the foundation for many other data structures.
- Have a single head node that serves as the list's first node.
- Maintenance is required to add or remove nodes.
