stevenbeales
12/27/2018 - 3:07 AM

Linked List

Linked lists are one of the basic data structures used in computer science. They have many direct applications and serve as the foundation for more complex data structures.

The list is comprised of a series of nodes as shown in the diagram. The head node is the node at the beginning of the list. Each node contains data and a link (or pointer) to the next node in the list. The list is terminated when a node's link is null. This is called the tail node.

Consider a one-way air travel itinerary. The trip could involve traveling through several airports (nodes) connected by air travel segments (links). In this example, the initial departure city is the head node and the final arrival city is the tail node.

Since the nodes use links to denote the next node in the sequence, the nodes are not required to be sequentially located in memory. These links also allow for quick insertion and removal of nodes as you will see in future exercises.

Common operations on a linked list may include:

  • adding nodes
  • removing nodes
  • finding a node
  • traversing (or travelling through) the linked list Linked lists typically contain unidirectional links (next node), but some implementations make use of bidirectional links (next and previous nodes).

With linked lists, because nodes are linked to from only one other node, you can't just go adding and removing nodes willy-nilly without doing a bit of maintenance.

Adding a new node to the beginning of the list requires you to link your new node to the current head node. This way, you maintain your connection with the following nodes in the list.

If you accidentally remove the single link to a node, that node's data and any following nodes could be lost to your application, leaving you with orphaned nodes.

To properly maintain the list when removing a node from the middle of a linked list, you need to be sure to adjust the link on the previous node so that it points to the following node.

Depending on the language, nodes which are not referenced are removed automatically. "Removing" a node is equivalent to removing all references to the node.

In Python, nodes which are not referenced will be removed for us automatically. If we take care of the references, an orphan node will be "removed" for us in a process called Garbage Collection.

A linked list only keeps track of the first node in the list. To traverse the list, it needs a method that loops through each node to find the following node.

.py
content_copyfile_download
# Example of implementing a linked list
class Node:
  def __init__(self, value, next_node=None):
    self.value = value
    self.next_node = next_node
    
  def get_value(self):
    return self.value
  
  def get_next_node(self):
    return self.next_node
  
  def set_next_node(self, next_node):
    self.next_node = next_node

class LinkedList:
  def __init__(self, value=None):
    self.head_node = Node(value)
  
  def get_head_node(self):
    return self.head_node
  
  def insert_beginning(self, new_value):
    new_node = Node(new_value)
    new_node.set_next_node(self.head_node)
    self.head_node = new_node
    
  def stringify_list(self):
    string_list = ""
    current_node = self.get_head_node()
    while current_node:
      if current_node.get_value() != None:
        string_list += str(current_node.get_value()) + "\n"
      current_node = current_node.get_next_node()
    return string_list
  
  def remove_node(self, value_to_remove):
    current_node = self.get_head_node()
    if current_node.get_value() == value_to_remove:
      self.head_node = current_node.get_next_node()
    else:
      while current_node:
        next_node = current_node.get_next_node()
        if next_node.get_value() == value_to_remove:
          current_node.set_next_node(next_node.get_next_node())
          current_node = None
        else:
          current_node = next_node

  def remove_all_nodes(self, value_to_remove):
    # Check value of current head node and loop as long as head node satisfies conditions
    current_node = self.get_head_node()
    while current_node:
      if current_node.get_value() == value_to_remove:
        self.head_node = current_node.get_next_node()
        current_node = self.get_head_node()
        print('head node removed')
      else:
        print('first loop broke due to head node not needing removal')
        break

   # If head node does not need to be removed check next node
    while current_node:
        next_node = current_node.get_next_node()
        if next_node == None:
          print('No next node so broke the loop')
          break
        if next_node.get_value() == value_to_remove:
          try:
            current_node.set_next_node(next_node.get_next_node())
            print('Next node is removed')
          except AttributeError:
            current_node.set_next_node(None)
            print('Next node needs to be removed and is last node')
            break
        else:
          current_node = next_node
          print('Next node did not match value')