Linked list, stacks, and queues - Sam647254/Programetoj GitHub Wiki

Linked list

The "list" data structure that you encountered in CS 135 is a linked list, specifically a singly linked list. It consists of nodes that hold a value and a pointer to the next node. The last node points to None.

class Node:
   def __init__(self, value, after):
      self.value = value
      self.after = after

A list is then just a wrapper around a Node. It supports the following operations: prepend (i.e. cons), head (i.e. first), and tail (i.e. rest):

class LinkedList:
   def __init__(self):
      self.list = None

   def prepend(self, new_value):
      self.list = Node(new_value, self.list)

   def head(self):
      if self.list is None:
         raise Exception("list is empty")
      return self.list.value

   def tail(self):
      if self.list is None:
         raise Exception("list is empty")
      return self.list.next

   def is_empty(self):
      return self.list is None

   def length(self):
      next_node = self.list
      count = 0
      while next_node is not None:
         count += 1
         next_node = next_node.after
      return count

All operations run in O(1) time, except for length which runs in O(n) time, in which n is the number of nodes.

Doubly linked list

In a doubly linked list, every node has a pointer to both the element before and after it.

class DoublyLinkedNode:
   def __init__(self, before, value, after):
      self.before = before
      self.value = value
      self.after = after

A doubly linked list holds a reference to both the head (the first element) and the tail (the last element):

class DoublyLinkedList:
   def __init__(self):
      self.head = None
      self.tail = None

   def prepend(self, new_value):
      new_head = DoublyLinkedNode(None, new_value, self.head)
      if self.head is not None:
         self.head.before = new_head
      if self.tail is None:
         self.tail = new_head
      self.head = new_head

   def append(self, new_value):
      new_tail = DoublyLinkedNode(self.tail, new_value, None)
      if self.tail is not None:
         self.tail.after = new_tail
      if self.head is None:
         self.head = new_tail
      self.tail = new_tail

   def length(self):
      next_node = self.head
      count = 0
      while next_node is not None:
         count += 1
         next_node = next_node.after
      return count

Stacks

A stack is a data structure that stores a sequence of data in which the entries are removed in the reversed order in which they are inserted (last in first out).

A stack supports the following operations:

• push: prepends a node onto a stack. O(1) time.
• pop: removes the last-pushed element from a stack. O(1) time.
• (optional) size/length/count: returns the size of a stack. O(1) time.

A stack can be implemented with a singly linked list, or even more simply the built-in list:

stack = []
stack.append(1) # push
stack.append(2) # push
len(stack) # => 2
stack.pop() # => 2
stack.pop() # => 1

Queue

A queue is a data structure that stores a sequence of data in which the first elements inserted will be the first to be removed (first in first out). It supports the following operations:

• enqueue/push: pushes a node to the end of a queue. O(1) time.
• dequeue/shift: removes a node from the beginning of a queue. O(1) time.
• (optional) size/length/count: returns the size of a queue. O(1) time.

A related data structure is called the "deque", or double-ended queue. It supports pushing and removing from both ends of the queue. The normal queue is a subset of the deque. The deque is built into Python.