Linked Lists
What is a linked list? Before we understand what a linked list is we need to understand what linked lists are made of.
Linked lists are made of nodes. A node references other objects, meaning that the data is not allocated in the node but instead the location of the data or a point in memory where the data is. When the data is requested from the node, the node finds the address that points to the data that is being requested and returns the data.
Another characteristic of a node is that it has properties to connect with other nodes. In single linked lists this property is conventionally called “next” to connect to the next node and in a double linked list, a node has an extra property called “previous” to connect to the previous node but this post will only focus on the single linked list.
The result are random locations in memory that are all linked together by pointers in contrast to an array where the memory is allocated in a linear space or one after the other and in the case of a dynamic array, as more data is added to the array, the array creates more space in advance and some times we might run into cases where the array is half empty. A linked list allows us to connect data from any place in memory and therefore adding more data to the linked list does not require expansion or doubling it in advance without wasting memory.
A linked list has two properties conventionally called “head” and “tail”. The head references the beginning of the linked list and the tail represent the last item of the linked list that points to “null” to indicate the end of the linked list. When traversing a singly linked list we start at the head and continue moving forward from one node to the next but in a double linked list it is possible to traverse forward and backward thanks to the extra property in the node that keeps a reference of the previous node.
Before deleting items from a linked list we have to be very careful because if we delete a node without assigning a reference to the next node, the connection is lost and therefore the rest of the data is lost.
Deleting node pseudocode in a single linked list:
Let’s say we want to delete a node in the middle of the linked list.
- We start at the head node of the linked list, therefore, we initialize a variable name node and assign the head of the linked list to the node.
- We initialize a variable name previous to keep track of the node before the one containing the given item and with an initial value of None.
- We create a flag to track if we found the given item and this variable can be named found with an initial value of false.
- We loop through or traverse the linked list until we find the node we want to delete or until the next is pointing to null to indicate the item we are looking for is not in the linked list.
- ==== If the node data is equal to the item:
- ======== we assigned to true the variable found, updating our flag.
- ==== if not:
- ======== previous is assign to node
- ======== node is assign to the next node
- If found is equal to true:
- ==== Check if we found the node in the middle of the linked list:
- ======== The next link in previous node is updated with the ======== node next link and node next is updated to None
- ==== If node is the head:
- ======== The head is updated to the node next link
- ======== the node next link is updated to None
- ==== If node is the tail:
- ======== Check if there’s a node before the node we found.
- ============ Unlink previous next updating link to None
- ======== assigned the tail to previous node
- If not found:
- ==== Raise a value error to indicating item not found.
Get Ramon Geronimo’s stories in your inbox
Join Medium for free to get updates from this writer.
Methods defined in a linked list:
- items(): Return a list of all items in the linked list.
- is_empty(): Return true if the linked list is empty or false otherwise.
- length(): Return the length of the linked list.
- get_at_index(index): Return the item at the given index or raise a value error if the given index is out of range of the size.
- insert_at_index(index, item): Insert the given item at the given index or raise a value error if the given index is out of range.
- append(item): Insert the given item at the tail of the linked list.
- prepend(item): Insert the given item at the head of the linked list.
- find(quality): Return an item from the linked list satisfying the given quality. In this case, quality can be anything (ex. quality = chocolate, when going for ice cream and asking for any flavor that has chocolate in it and the return can be chocolate chip ice cream if it’s available in the linked list)
- replace(old_item, new_item): Replace the given old_item with a given new_item or raise a value error if the old_item is not found.
- delete(item): delete the given item from the linked list or raise a value error if the item is not found.
Conclusion
The same way we can customize a linked list from a single to a double linked list by adding an extra property called previous, we can include a size property to return the length of the linked list without traversing each node and also include custom methods for specific needs.







![Python DSA Coding Interview Series:16/29[Graph Traversal: BFS and DFS on Grids and Networks]](https://miro.medium.com/v2/resize:fit:1358/format:webp/1*q6LJf2FZs9hZCjbrBcndSw.png)
