Data Structures - Arrays and Array-ish

Arrays vs. Linked Lists

Arrays and linked lists are fundamental data structures, each with unique advantages and drawbacks. Alan Underwood explains that linked lists allow for efficient insertion and removal of elements from the middle, unlike arrays, which are better suited for situations requiring rapid access to elements by index 1. Michael Outlaw adds that arrays are preferable when dealing with large datasets due to their memory efficiency 2. However, linked lists offer flexibility, especially when the size of the data structure is not fixed 3.

Linked lists can cheaply add or move items out of the middle, and lists can only cheaply add things to the end.

--- Alan Underwood

In C#, arrays are typically stored on the heap, but their location can vary based on initialization, as Joe Zack notes 4.

   

Stack Operations

Stacks are a crucial data structure in computer science, often used for parsing and managing state. Alan Underwood highlights their efficiency in solving problems that require tracking conditions without excessive data revisiting 5. The stack operates on a Last In, First Out (LIFO) principle, with key operations being push, pop, and peek 6.

If it seems like I'm having to do a lot of work to track the state that I'm in, if I'm doing anything that remotely feels like or looks like parsing, and there's a good chance that a stack is going to come into play.

--- Alan Underwood

Michael Outlaw uses the analogy of a stack of pancakes to explain these operations, emphasizing the importance of peeking to view the top element without removing it.

   

Queue Types

Queues, including their variations like priority queues, are essential for managing ordered data. Joe Zack describes priority queues as similar to standard queues but with elements assigned priorities, affecting their retrieval order 7. Michael Outlaw explains that priority queues are often implemented using binary heaps, which optimize the process of maintaining order based on priority 8.

The highest priority want to go first, and then if all the priorities are the same, and then it falls back to the standard queuing method, which is the FIFO.

--- Joe Zack

Additionally, Alan Underwood discusses the utility of circular queues, which allow for efficient use of memory by overwriting old data when new data is added 9.