7. Linear Data Structures

---

Nodes

Node

• the fundamental building blocks of many computer science data structures

• form the basis for linked lists, stacks, queues, trees, and more

• node contains data and links to other nodes
  

• can have diff datatype

• links : pointer(points another node) Null link -> end of node/link path
  

• orphaned if there are no existing links to them

python nodes

class Node:
  def __init__(self, value, link_node=None):
    self.value = value
    self.link_node = link_node
    
    # Define your get_value and get_link_node methods below:
  def get_value(self):
    return self.value

  def get_link_node(self):
    return self.link_node
    
  # Define your set_link_node method below:
  def set_link_node(self, link_node):
    self.link_node = link_node
    
  # Add your code below:

yacko = Node("likes to yak")
wacko = Node("has a penchant for hoarding snacks")
dot = Node("enjoys spending time in movie lots")

yacko.set_link_node(dot)
dot.set_link_node(wacko)

dots_data = yacko.get_link_node().get_value()
wackos_data = dot.get_link_node().get_value()
print(dots_data)
print(wackos_data)

---

Linked Lists

Linked List

• linear data structure where elements are not stored at contiguous location
• list : comprised of a series of nodes
• Can be unidirectional or bidirectional
• head node : initial node of link
• tail node : node's link == null
• on a linked list... add / remove / find / traversing nodes

adding a new head node

• link new head node to current head node

linked list w/ python : Node Implementation

• class Node building
• building class LinkedList : to modify linkedlist

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

• can only track the first node of list

---

Stacks

stack

• data structure which contains an ordered set of data.
• methods for interaction:

  push() : add data to the top
  pop() : returns and removes data from top
  peek() : returns data from top without removing

• stack overflow: Attempting to push a node in a full stack
• last in, first out (LIFO) protoco

stack w/ python

from node import Node

class Stack:
  def __init__(self, limit=1000):
    self.top_item = None
    self.size = 0
    self.limit = limit
  
  def push(self, value):
    if self.has_space():
      item = Node(value)
      item.set_next_node(self.top_item)
      self.top_item = item
      self.size += 1
    else:
      print("All out of space!")

  def pop(self):
    if self.size > 0:
      item_to_remove = self.top_item
      self.top_item = item_to_remove.get_next_node()
      self.size -= 1
      return item_to_remove.get_value()
    else:
      print("This stack is totally empty.")
  
  def peek(self):
    if self.size > 0:
      return self.top_item.get_value()
    else:
      print("Nothing to see here!")
  
  def has_space(self):
    return self.limit > self.size
  
  def is_empty(self):
    return self.size == 0

towers of hanoi

---

Queues

Queue

• data structure which contains an ordered set of data.

• First In, First Out or FIFO structure.

• method

  Enqueue : adds a node to the back of the queue
  Dequeue : removes node at the front of the queue
  Peek : returns value of node at the front of the queue, without removing it

• queue underflow : dequeueing data from an empty queue

Queue w/ python

from node import Node

class Queue:
  def __init__(self, max_size=None):
    self.head = None
    self.tail = None
    self.max_size = max_size
    self.size = 0
    
  def enqueue(self, value):
    if self.has_space():
      item_to_add = Node(value)
      print("Adding " + str(item_to_add.get_value()) + " to the queue!")
      if self.is_empty():
        self.head = item_to_add
        self.tail = item_to_add
      else:
        self.tail.set_next_node(item_to_add)
        self.tail = item_to_add
      self.size += 1
    else:
      print("Sorry, no more room!")
         
  def dequeue(self):
    if self.get_size() > 0:
      item_to_remove = self.head
      print(str(item_to_remove.get_value()) + " is served!")
      if self.get_size() == 1:
        self.head = None
        self.tail = None
      else:
        self.head = self.head.get_next_node()
      self.size -= 1
      return item_to_remove.get_value()
    else:
      print("The queue is totally empty!")
  
  def peek(self):
    if self.size > 0:
      return self.head.get_value()
    else:
      print("No orders waiting!")
  
  def get_size(self):
    return self.size
  
  def has_space(self):
    if self.max_size == None:
      return True
    else:
      return self.max_size > self.get_size()
    
  def is_empty(self):
    return self.size == 0