mutecipher - data structures

A data structure is a specialized format for organizing and storing data to make it accessible and efficient for computation.

Linked List

A Linked List is a linear data structure that consists of a sequence of nodes, each containing an element and a reference to the next node in the sequence. The first node is called the head or the beginning of the list. Nodes store data as well as pointers to the next nodes, creating a dynamic link between them. Linked Lists are commonly used when dealing with large data sets that need to be frequently modified, such as lists, queues, and stacks. The time complexity for common operations like insertion, deletion, and traversal is generally O(1) at the head of the list, but can vary depending on the implementation and location within the list. Space complexity for a Linked List is O(n), where n is the number of elements in the list.

Pros	Cons
Dynamic data structure (shrink/grow at runtime)	Requires more memory when compared to an array
No need to pre-allocate memory	Traversing a linked list is more time consuming than an array
Stacks and Queues are often easily implemented using a linked list	Random access is no possible due to it's dynamic nature
Insertion and deletion operations tend to be easier using a linked list	Certain operations, such as searchinng, are slower using a linked list
Efficient for large datasets	More complex to implement than an array
Ability to add or remove elements at any position	Not ideal for small datasets over an array

Other implementations that should also be explored:

Singly linked lists

Doubly (Two way) linked lists

Circular linked lists

Circular doubly linked lists

class LinkedList
  attr_reader :head

  def initialize
    @head = nil
  end

  def append(value)
    if @head.nil?
      @head = Node.new(value)
      return
    end

    node = @head

    loop do
      break if node.next.nil?
      node = node.next
    end

    node.next = Node.new(value)
  end

  def append_after(n, value)
    node = @head
    new_node = Node.new(value)

    loop do
      break if node.nil?
      break if node == n
      node = node.next
    end

    temp = node.next
    node.next = new_node
    new_node.next = temp
  end

  def prepend(value)
    node = Node.new(value)
    node.next = @head
    @head = node
  end

  def prepend_before(n, value)
    new_node = Node.new(value)

    if @head == n
      temp = @head.next
      new_node.next = @head
      @head = new_node
      return
    end

    node = @head

    loop do
      break if node.next.nil?
      break if node.next == n
      node = node.next
    end

    temp = node.next
    node.next = new_node
    new_node.next = temp
  end

  def delete(value)
    node = @head

    loop do
      break if node.nil?
      break if node.next.value == value
      node = node.next
    end

    node.next = node.next.next
  end

  def delete_end
    node = @head

    loop do
      break if node.next.nil?
      node = node.next
    end

    node.next = nil
  end

  def delete_all
    @head = nil
  end

  def find(value)
    node = @head

    loop do
      break if node.nil?
      break if node.value == value
      node = node.next
    end

    return node
  end

  def values
    node = @head
    result = []

    loop do
      break if node.nil?
      result << node.value
      node = node.next
    end

    return result
  end

  def size
    values.length
  end
end

class Node
  attr_accessor :value, :next

  def initialize(value)
    @value = value
    @next = nil
  end
end

Stack

A Stack is a simple linear data structure that follows the Last-In, First-Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. The basic operations for a stack include push, which adds an element to the top of the stack, and pop, which removes the topmost element from the stack. Other common operations include peek, which returns the topmost element without removing it, and checking if the stack is empty or full. Stacks are commonly used for implementing function calls in programming languages, reverse iterations, and evaluating expressions with parentheses. The time complexity for most basic stack operations is O(1), making them highly efficient. Space complexity for a Stack is O(n), where n is the maximum number of elements it can hold.

Pros	Cons
Easy to implement	Limited capacity
Efficient memory utilization	No random access
Fast access time	Memory management
Enables undo/redo operations	Stack overflow/underflow
	Recursive function call limitations

This structure uses a Last in, first out (LIFO) principle.

class Stack
  attr_reader :items

  def initialize
    @items = Array.new
  end

  def push(item)
    @items.push(item)
  end

  def pop
    @items.pop
  end

  def size
    @items.length
  end
end

Queue

A Queue is a linear data structure that follows the First-In, First-Out (FIFO) principle, meaning the first element added to the queue is the first one to be removed. The basic operations for a queue include enqueue, which adds an element to the end of the queue, and dequeue, which removes the frontmost element from the queue. Other common operations include checking if the queue is empty or full and peeking at the frontmost element without removing it. Queues are commonly used in various applications such as message passing systems, real-time processing, and simulating different scenarios where data needs to be processed in the order they arrived. The time complexity for most basic queue operations is O(1), making them highly efficient. Space complexity for a Queue is O(n), where n is the maximum number of elements it can hold.

Pros	Cons
Efficiently manage large amounts of data	Insertion/deletion of elements from the middle are time consuming
Insertion/deletion of elements can be performed easily due to FIFO	Limited space
Useful when used by multiple consumers	Searching takes `0(n)`
Fast for inter-process communication	Maximum size must be defined prior (non-dynamic)
Used in the implementation of other data structures

This structure uses a First in, first out (FIFO) principle.

class Queue
  attr_reader :items

  def initialize
    @items = Array.new
  end

  def enqueue(item)
    @items.unshift(item)
  end

  def dequeue
    @items.pop
  end

  def size
    @items.length
  end
end