# Data Structures ## Properties of Data Structures ### Data Structure Organization The main three types of organization are: - Linear - Tree - Graph Almost all other structures are a subset of these main types (although pretty much everything can be considered some type of graph due to the nature of connections). > [!info] **Major Structure Type** > - [[Linear Data Structures]] > - [[Tree Data Structures]] > - [[Graph Theory|Graph Data Structures]] > - [[Hash Functions]] ### Concrete vs Abstract Data Types An **abstract data type** is composed of a collection of data that often involves a layer of *abstraction* (as the name implies). In abstract data types, users *don’t directly interact* with the data structures, instead they can *interface with the structure* by using a given set of operations. - Ex: *queues* and *stacks* are abstract data which can be implemented using a linked list data structure. - While the structure within both data types is the same, the methods associated with them can drastically change how they behave. technically even most tree data structures can be implemented using an arraylist ### Probabilistic vs Deterministic Structures > See also: [[Probability Theory]] A lot of high-performing data structures aren’t feasible in real-world applications due to the high spacial complexity associated with them. Instead, we often choose to sacrifice a small percent of accuracy/precision and incorporate some level of randomness (probability) into data structures/algorithms. A probabilistic data structure may prevent the worst case scenario, but the “expected” run time associated with it will not always be achieved in real-life due to the nature of randomness ## Data Structure Organization ### Self-Balancing Functions - hash tables - [[Skip Lists]] - treaps The self-balancing nature of certain data structures is perhaps easiest to understand with tree-based structures. - abstract data types - linked memory - recursive structures tags: related: - "[[Computer Science.canvas|Computer Science]]" - "[[Computer Algorithms]]" --- # Data Structures ## Properties of Data Structures ### Data Structure Organization The main three types of organization are: - Linear - Tree - Graph Almost all other structures are a subset of these main types (although pretty much everything can be considered some type of graph due to the nature of connections). > [!info] **Major Structure Type** > - [[Linear Data Structures]] > - [[Tree Data Structures]] > - [[Graph Theory|Graph Data Structures]] > - [[Hash Functions]] ### Concrete vs Abstract Data Types An **abstract data type** is composed of a collection of data that often involves a layer of *abstraction* (as the name implies). In abstract data types, users *don’t directly interact* with the data structures, instead they can *interface with the structure* by using a given set of operations. - Ex: *queues* and *stacks* are abstract data which can be implemented using a linked list data structure. - While the structure within both data types is the same, the methods associated with them can drastically change how they behave. technically even most tree data structures can be implemented using an arraylist ### Probabilistic vs Deterministic Structures > See also: [[Probability Theory]] A lot of high-performing data structures aren’t feasible in real-world applications due to the high spacial complexity associated with them. Instead, we often choose to sacrifice a small percent of accuracy/precision and incorporate some level of randomness (probability) into data structures/algorithms. A probabilistic data structure may prevent the worst case scenario, but the “expected” run time associated with it will not always be achieved in real-life due to the nature of randomness ## Data Structure Organization ### Self-Balancing Functions - hash tables - [[Skip Lists]] - treaps The self-balancing nature of certain data structures is perhaps easiest to understand with tree-based structures. ### Memory Management #### Heap vs Stack Space heap vs stack space Programs or data structures which rely on dynamic memory will interact with the heap space #### Linked Memory **Linked memory** is a method of storing data in which each data element is stored separately in memory and linked to its neighboring elements using pointers or references. Commonly used in linked data structures, such as: - linked lists, trees, and graphs. For example, in [[linked lists]] each node contains a data element and a pointer to the next node in the list. #### Structural Recursion > See also: [[Recursion]] **Recursive structures** are data structures *that contain references to themselves*. They can be defined recursively, meaning the structure is defined in terms of itself. ![[Structural Recursion.png|400]] For example, a binary tree can be defined recursively as a root node that has two child nodes, each of which is a binary tree. Another example is a linked list, where each node contains a reference to the next node, forming a recursive structure. ### Memory Management #### Heap vs Stack Space heap vs stack space Programs or data structures which rely on dynamic memory will interact with the heap space #### Linked Memory **Linked memory** is a method of storing data in which each data element is stored separately in memory and linked to its neighboring elements using pointers or references. Commonly used in linked data structures, such as: - linked lists, trees, and graphs. For example, in [[linked lists]] each node contains a data element and a pointer to the next node in the list. #### Structural Recursion > See also: [[Recursion]] **Recursive structures** are data structures *that contain references to themselves*. They can be defined recursively, meaning the structure is defined in terms of itself. ![[Structural Recursion.png|400]] For example, a binary tree can be defined recursively as a root node that has two child nodes, each of which is a binary tree. Another example is a linked list, where each node contains a reference to the next node, forming a recursive structure.