Data Structures - Revision history

Wordpad: BloomWiki: Data Structures

2026-04-25T01:49:45Z

BloomWiki: Data Structures

← Older revision		Revision as of 01:49, 25 April 2026
Line 1:		Line 1:
			<div style="background-color: #4B0082; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
	{{BloomIntro}}		{{BloomIntro}}
	Data Structures are specialized formats for organizing, processing, retrieving, and storing data in a computer. While algorithms are the "logic," data structures are the "vessels" that hold the information. Choosing the right data structure is one of the most important decisions a programmer makes; it can be the difference between an application that is lightning-fast and one that crashes. From simple lists and arrays to complex graphs and hash tables, data structures provide the structural integrity for all software systems.		Data Structures are specialized formats for organizing, processing, retrieving, and storing data in a computer. While algorithms are the "logic," data structures are the "vessels" that hold the information. Choosing the right data structure is one of the most important decisions a programmer makes; it can be the difference between an application that is lightning-fast and one that crashes. From simple lists and arrays to complex graphs and hash tables, data structures provide the structural integrity for all software systems.
			</div>

	== Remembering ==		__TOC__

			<div style="background-color: #000080; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Remembering</span> ==
	* '''Data Structure''' — A way of organizing data so that it can be used efficiently.		* '''Data Structure''' — A way of organizing data so that it can be used efficiently.
	* '''Array''' — A collection of items stored at contiguous memory locations; indexed by number.		* '''Array''' — A collection of items stored at contiguous memory locations; indexed by number.
Line 17:		Line 22:
	* '''Dynamic Array''' — An array that can resize itself during execution (e.g., Python list).		* '''Dynamic Array''' — An array that can resize itself during execution (e.g., Python list).
	* '''Trie''' — A specialized tree used for searching strings (e.g., for autocomplete).		* '''Trie''' — A specialized tree used for searching strings (e.g., for autocomplete).
			</div>

	== Understanding ==		<div style="background-color: #006400; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Understanding</span> ==
	Data structures represent tradeoffs between '''Time''' (access speed) and '''Space''' (memory usage).		Data structures represent tradeoffs between '''Time''' (access speed) and '''Space''' (memory usage).

Line 31:		Line 38:

	'''The Power of Abstraction''': We often talk about "Stacks" or "Queues" as '''Abstract Data Types'''. You can build a Stack using an Array ''or'' a Linked List; the "user" doesn't care about the implementation as long as it follows the "Last-In, First-Out" rule.		'''The Power of Abstraction''': We often talk about "Stacks" or "Queues" as '''Abstract Data Types'''. You can build a Stack using an Array ''or'' a Linked List; the "user" doesn't care about the implementation as long as it follows the "Last-In, First-Out" rule.
			</div>

	== Applying ==		<div style="background-color: #8B0000; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Applying</span> ==
	'''Implementing a Stack vs. Queue:'''		'''Implementing a Stack vs. Queue:'''
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
Line 63:		Line 72:
	: '''Dictionary / Database''' → Hash Tables (look up word/ID instantly).		: '''Dictionary / Database''' → Hash Tables (look up word/ID instantly).
	: '''AI / Pathfinding''' → Trees and Heaps.		: '''AI / Pathfinding''' → Trees and Heaps.
			</div>

	== Analyzing ==		<div style="background-color: #8B4500; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Analyzing</span> ==
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Data Structure Time Complexities		\|+ Data Structure Time Complexities
Line 79:		Line 90:

	'''The Importance of Memory Layout''': In modern hardware, the physical arrangement of data matters. Arrays are fast not just because of their math, but because they sit together in memory, making them "Cache Friendly." Linked lists, which scatter data across memory, can be significantly slower in practice due to "cache misses."		'''The Importance of Memory Layout''': In modern hardware, the physical arrangement of data matters. Arrays are fast not just because of their math, but because they sit together in memory, making them "Cache Friendly." Linked lists, which scatter data across memory, can be significantly slower in practice due to "cache misses."
			</div>

	== Evaluating ==		<div style="background-color: #483D8B; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Evaluating</span> ==
	Evaluating a structure:		Evaluating a structure:
	# '''Frequency of operations''': Will we be doing more "lookups" or more "insertions"?		# '''Frequency of operations''': Will we be doing more "lookups" or more "insertions"?
Line 86:		Line 99:
	# '''Persistence''': Does the data need to be saved to a disk (requiring B-Trees)?		# '''Persistence''': Does the data need to be saved to a disk (requiring B-Trees)?
	# '''Concurrency''': Can multiple "threads" access the structure at once without breaking it?		# '''Concurrency''': Can multiple "threads" access the structure at once without breaking it?
			</div>

	== Creating ==		<div style="background-color: #2F4F4F; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Creating</span> ==
	Future Frontiers:		Future Frontiers:
	# '''Probabilistic Data Structures''': Structures like "Bloom Filters" that use very little memory but can tell you with 99% certainty if an item is in a set.		# '''Probabilistic Data Structures''': Structures like "Bloom Filters" that use very little memory but can tell you with 99% certainty if an item is in a set.
Line 97:		Line 112:
	[[Category:Programming]]		[[Category:Programming]]
	[[Category:Data Structures]]		[[Category:Data Structures]]
			</div>

Wordpad: BloomWiki: Data Structures

2026-04-23T14:37:17Z

BloomWiki: Data Structures

← Older revision		Revision as of 14:37, 23 April 2026
Line 81:		Line 81:

	== Evaluating ==		== Evaluating ==
	Evaluating a structure: ~~(1)~~ '''Frequency of operations''': Will we be doing more "lookups" or more "insertions"? ~~(2)~~ '''Memory constraints''': Can we afford the extra memory for pointers in a tree or the "empty" space in a hash table? ~~(3)~~ '''Persistence''': Does the data need to be saved to a disk (requiring B-Trees)? ~~(4)~~ '''Concurrency''': Can multiple "threads" access the structure at once without breaking it?		Evaluating a structure:
			# '''Frequency of operations''': Will we be doing more "lookups" or more "insertions"?
			# '''Memory constraints''': Can we afford the extra memory for pointers in a tree or the "empty" space in a hash table?
			# '''Persistence''': Does the data need to be saved to a disk (requiring B-Trees)?
			# '''Concurrency''': Can multiple "threads" access the structure at once without breaking it?

	== Creating ==		== Creating ==
	Future Frontiers: ~~(1)~~ '''Probabilistic Data Structures''': Structures like "Bloom Filters" that use very little memory but can tell you with 99% certainty if an item is in a set. ~~(2)~~ '''Persistent Data Structures''': Structures used in functional programming (like Clojure) that "remember" their previous versions without copying all the data. ~~(3)~~ '''Succinct Data Structures''': Pushing the mathematical limits to store data in the theoretical minimum amount of space (close to the entropy limit). ~~(4)~~ '''Neural Data Structures''': Using machine learning to "learn" the optimal index for a specific dataset.		Future Frontiers:
			# '''Probabilistic Data Structures''': Structures like "Bloom Filters" that use very little memory but can tell you with 99% certainty if an item is in a set.
			# '''Persistent Data Structures''': Structures used in functional programming (like Clojure) that "remember" their previous versions without copying all the data.
			# '''Succinct Data Structures''': Pushing the mathematical limits to store data in the theoretical minimum amount of space (close to the entropy limit).
			# '''Neural Data Structures''': Using machine learning to "learn" the optimal index for a specific dataset.

	[[Category:Computer Science]]		[[Category:Computer Science]]
	[[Category:Programming]]		[[Category:Programming]]
	[[Category:Data Structures]]		[[Category:Data Structures]]

Wordpad: BloomWiki: Data Structures

2026-04-23T14:28:04Z

BloomWiki: Data Structures

← Older revision		Revision as of 14:28, 23 April 2026
Line 30:		Line 30:
	* '''Graphs''': The most flexible structure. Used to model the Internet, social networks (Facebook "friends"), or road maps.		* '''Graphs''': The most flexible structure. Used to model the Internet, social networks (Facebook "friends"), or road maps.

	'''The Power of Abstraction''': We often talk about "Stacks" or "Queues" as '''Abstract Data Types'''. You can build a Stack using an Array or a Linked List; the "user" doesn't care about the implementation as long as it follows the "Last-In, First-Out" rule.		'''The Power of Abstraction''': We often talk about "Stacks" or "Queues" as '''Abstract Data Types'''. You can build a Stack using an Array ''or'' a Linked List; the "user" doesn't care about the implementation as long as it follows the "Last-In, First-Out" rule.

	== Applying ==		== Applying ==

Wordpad: BloomWiki: Data Structures

2026-04-23T14:22:07Z

BloomWiki: Data Structures

← Older revision		Revision as of 14:22, 23 April 2026
Line 19:		Line 19:

	== Understanding ==		== Understanding ==
	Data structures represent tradeoffs between Time (access speed) and Space (memory usage).		Data structures represent tradeoffs between '''Time''' (access speed) and '''Space''' (memory usage).

	Linear vs. Non-Linear Structures:		'''Linear vs. Non-Linear Structures''':
	* Arrays: Best for random access (I want the 500th item). Hard to resize or insert in the middle.		* '''Arrays''': Best for random access (I want the 500th item). Hard to resize or insert in the middle.
	* Linked Lists: Best for frequent insertions/deletions. Slow to find a specific item because you have to "walk" from the start.		* '''Linked Lists''': Best for frequent insertions/deletions. Slow to find a specific item because you have to "walk" from the start.
	* Hash Tables: The "Magic" structure. By turning a name (key) into a number (hash), you can jump directly to the data. This is how high-performance databases work.		* '''Hash Tables''': The "Magic" structure. By turning a name (key) into a number (hash), you can jump directly to the data. This is how high-performance databases work.

	Hierarchical and Network Structures:		'''Hierarchical and Network Structures''':
	* Trees: Used whenever data is nested (folders on your computer, HTML on a webpage).		* '''Trees''': Used whenever data is nested (folders on your computer, HTML on a webpage).
	* Graphs: The most flexible structure. Used to model the Internet, social networks (Facebook "friends"), or road maps.		* '''Graphs''': The most flexible structure. Used to model the Internet, social networks (Facebook "friends"), or road maps.

	The Power of Abstraction: We often talk about "Stacks" or "Queues" as Abstract Data Types. You can build a Stack using an Array or a Linked List; the "user" doesn't care about the implementation as long as it follows the "Last-In, First-Out" rule.		'''The Power of Abstraction''': We often talk about "Stacks" or "Queues" as '''Abstract Data Types'''. You can build a Stack using an Array or a Linked List; the "user" doesn't care about the implementation as long as it follows the "Last-In, First-Out" rule.

	== Applying ==		== Applying ==
Line 78:		Line 78:
	\|}		\|}

	The Importance of Memory Layout: In modern hardware, the physical arrangement of data matters. Arrays are fast not just because of their math, but because they sit together in memory, making them "Cache Friendly." Linked lists, which scatter data across memory, can be significantly slower in practice due to "cache misses."		'''The Importance of Memory Layout''': In modern hardware, the physical arrangement of data matters. Arrays are fast not just because of their math, but because they sit together in memory, making them "Cache Friendly." Linked lists, which scatter data across memory, can be significantly slower in practice due to "cache misses."

	== Evaluating ==		== Evaluating ==
	Evaluating a structure: (1) Frequency of operations: Will we be doing more "lookups" or more "insertions"? (2) Memory constraints: Can we afford the extra memory for pointers in a tree or the "empty" space in a hash table? (3) Persistence: Does the data need to be saved to a disk (requiring B-Trees)? (4) Concurrency: Can multiple "threads" access the structure at once without breaking it?		Evaluating a structure: (1) '''Frequency of operations''': Will we be doing more "lookups" or more "insertions"? (2) '''Memory constraints''': Can we afford the extra memory for pointers in a tree or the "empty" space in a hash table? (3) '''Persistence''': Does the data need to be saved to a disk (requiring B-Trees)? (4) '''Concurrency''': Can multiple "threads" access the structure at once without breaking it?

	== Creating ==		== Creating ==
	Future Frontiers: (1) Probabilistic Data Structures: Structures like "Bloom Filters" that use very little memory but can tell you with 99% certainty if an item is in a set. (2) Persistent Data Structures: Structures used in functional programming (like Clojure) that "remember" their previous versions without copying all the data. (3) Succinct Data Structures: Pushing the mathematical limits to store data in the theoretical minimum amount of space (close to the entropy limit). (4) Neural Data Structures: Using machine learning to "learn" the optimal index for a specific dataset.		Future Frontiers: (1) '''Probabilistic Data Structures''': Structures like "Bloom Filters" that use very little memory but can tell you with 99% certainty if an item is in a set. (2) '''Persistent Data Structures''': Structures used in functional programming (like Clojure) that "remember" their previous versions without copying all the data. (3) '''Succinct Data Structures''': Pushing the mathematical limits to store data in the theoretical minimum amount of space (close to the entropy limit). (4) '''Neural Data Structures''': Using machine learning to "learn" the optimal index for a specific dataset.

	[[Category:Computer Science]]		[[Category:Computer Science]]
	[[Category:Programming]]		[[Category:Programming]]
	[[Category:Data Structures]]		[[Category:Data Structures]]

Wordpad: BloomWiki: Data Structures

2026-04-23T13:32:52Z

BloomWiki: Data Structures

New page

{{BloomIntro}}
Data Structures are specialized formats for organizing, processing, retrieving, and storing data in a computer. While algorithms are the "logic," data structures are the "vessels" that hold the information. Choosing the right data structure is one of the most important decisions a programmer makes; it can be the difference between an application that is lightning-fast and one that crashes. From simple lists and arrays to complex graphs and hash tables, data structures provide the structural integrity for all software systems.

== Remembering ==
* '''Data Structure''' — A way of organizing data so that it can be used efficiently.
* '''Array''' — A collection of items stored at contiguous memory locations; indexed by number.
* '''Linked List''' — A linear collection of data elements where each element points to the next.
* '''Stack''' — A "Last-In, First-Out" (LIFO) structure (like a stack of plates).
* '''Queue''' — A "First-In, First-Out" (FIFO) structure (like a line at a store).
* '''Hash Table''' — A structure that maps "keys" to "values" using a hash function (O(1) lookup).
* '''Tree''' — A hierarchical structure with a "root" and "child" nodes (e.g., Binary Search Tree).
* '''Graph''' — A set of nodes (vertices) connected by lines (edges); used to model networks.
* '''Heap''' — A specialized tree-based structure used for priority queues.
* '''Set''' — A collection of distinct elements with no specific order.
* '''Pointer''' — A variable that stores the memory address of another variable.
* '''Abstract Data Type (ADT)''' — A mathematical model for data types (defines what it does, not how it's implemented).
* '''Dynamic Array''' — An array that can resize itself during execution (e.g., Python list).
* '''Trie''' — A specialized tree used for searching strings (e.g., for autocomplete).

== Understanding ==
Data structures represent tradeoffs between **Time** (access speed) and **Space** (memory usage).

**Linear vs. Non-Linear Structures**:
* **Arrays**: Best for random access (I want the 500th item). Hard to resize or insert in the middle.
* **Linked Lists**: Best for frequent insertions/deletions. Slow to find a specific item because you have to "walk" from the start.
* **Hash Tables**: The "Magic" structure. By turning a name (key) into a number (hash), you can jump directly to the data. This is how high-performance databases work.

**Hierarchical and Network Structures**:
* **Trees**: Used whenever data is nested (folders on your computer, HTML on a webpage).
* **Graphs**: The most flexible structure. Used to model the Internet, social networks (Facebook "friends"), or road maps.

**The Power of Abstraction**: We often talk about "Stacks" or "Queues" as **Abstract Data Types**. You can build a Stack using an Array *or* a Linked List; the "user" doesn't care about the implementation as long as it follows the "Last-In, First-Out" rule.

== Applying ==
'''Implementing a Stack vs. Queue:'''
<syntaxhighlight lang="python">
class Stack:
"""LIFO: Last-In, First-Out"""
def __init__(self): self.items = []
def push(self, x): self.items.append(x)
def pop(self): return self.items.pop()

class Queue:
"""FIFO: First-In, First-Out"""
def __init__(self): self.items = []
def enqueue(self, x): self.items.append(x)
def dequeue(self): return self.items.pop(0)

# Use Cases
s = Stack(); q = Queue()
for x in ["First", "Second", "Third"]:
s.push(x); q.enqueue(x)

print(f"Stack Pop (LIFO): {s.pop()}") # Third
print(f"Queue Dequeue (FIFO): {q.dequeue()}") # First
# Stacks are used for 'Undo' buttons; Queues for printer tasks.
</syntaxhighlight>

; Data Structures in Action
: '''Social Networks''' → Graphs (users as nodes, friendships as edges).
: '''Excel / Spreadsheets''' → 2D Arrays.
: '''Web Browsers''' → Stacks (the 'Back' button uses a history stack).
: '''Dictionary / Database''' → Hash Tables (look up word/ID instantly).
: '''AI / Pathfinding''' → Trees and Heaps.

== Analyzing ==
{| class="wikitable"
|+ Data Structure Time Complexities
! Structure !! Access !! Search !! Insertion !! Deletion
|-
| Array || O(1) || O(n) || O(n) || O(n)
|-
| Stack / Queue || O(n) || O(n) || O(1) || O(1)
|-
| Hash Table || N/A || O(1) || O(1) || O(1)
|-
| Binary Search Tree || O(log n) || O(log n) || O(log n) || O(log n)
|}

**The Importance of Memory Layout**: In modern hardware, the physical arrangement of data matters. Arrays are fast not just because of their math, but because they sit together in memory, making them "Cache Friendly." Linked lists, which scatter data across memory, can be significantly slower in practice due to "cache misses."

== Evaluating ==
Evaluating a structure: (1) **Frequency of operations**: Will we be doing more "lookups" or more "insertions"? (2) **Memory constraints**: Can we afford the extra memory for pointers in a tree or the "empty" space in a hash table? (3) **Persistence**: Does the data need to be saved to a disk (requiring B-Trees)? (4) **Concurrency**: Can multiple "threads" access the structure at once without breaking it?

== Creating ==
Future Frontiers: (1) **Probabilistic Data Structures**: Structures like "Bloom Filters" that use very little memory but can tell you with 99% certainty if an item is in a set. (2) **Persistent Data Structures**: Structures used in functional programming (like Clojure) that "remember" their previous versions without copying all the data. (3) **Succinct Data Structures**: Pushing the mathematical limits to store data in the theoretical minimum amount of space (close to the entropy limit). (4) **Neural Data Structures**: Using machine learning to "learn" the optimal index for a specific dataset.

[[Category:Computer Science]]
[[Category:Programming]]
[[Category:Data Structures]]