Sitemap

Linked Lists

5 min readMay 3, 2019

--

Linked List

What is a linked list? Before we understand what a linked list is we need to understand what linked lists are made of.

Node

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.

Press enter or click to view image in full size
Memory
Press enter or click to view image in full size
Node and Memory Reference

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.

Press enter or click to view image in full size
Nodes
Press enter or click to view image in full size

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.

Press enter or click to view image in full size
Head and Tail

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.

Press enter or click to view image in full size
Single Linked List

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.

Press enter or click to view image in full size
Lost Node After Deleting Link

Deleting node pseudocode in a single linked list:

Let’s say we want to delete a node in the middle of the linked list.

Press enter or click to view image in full size
Deleting a Node

    Get Ramon Geronimo’s stories in your inbox

    Join Medium for free to get updates from this writer.

  • 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.
Press enter or click to view image in full size
Previous Next Link Updated to Node Next Link
Press enter or click to view image in full size
After Updating Node Next to None, The Reference Gets Lost or Deleted

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.

--

--