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