Basic Data Structures Overview

Study Notes

Data Structures are used to organize and store data for the purpose of accessing it efficiently.
Linear data structures have data elements stored in a sequential manner, such as Arrays, Linked Lists, Stacks, and Queues.
Non-linear data structures have data elements stored in a non-sequential manner, such as Trees, Graphs, and Hash Tables.

The choice of a data structure depends on how complex the relationships are within the data and how easy it is to process.

In a Linear data structure, values are arranged in a straight line.
- Arrays have a fixed size and can store data of the same type.
- Linked Lists have a variable size, enabling them to grow or shrink as needed, and can store data of the same type.
- Stacks follow a "Last-In, First-Out" (LIFO) principle, with data added and removed from the top.
- Queues follow a "First-In, First-Out" (FIFO) principle, with data added at the back and removed from the front.
- Priority Queues allow adding elements at any position, but elements are removed based on their assigned priority (highest priority first).
In a Non-Linear data structure, values are not organized in a straight line, and they can have branching structures.
- Hash Tables use a "hash function" to organize data, making searching for specific elements fast.
- Trees organize data in a hierarchical structure, with branches emanating from a root node.
- Graphs are more general branching structures, offering more freedom in connections than trees.

Homogenous data structures store data of the same type.
- Arrays are an example of homogenous data structures.
Non-Homogenous data structures store data of different types.
- Structures and Classes are examples of non-homogenous data structures.

ADTs store data and offer operations to access or modify it.
ADTs are designed to support abstracting, encapsulating, and hiding information.
- Abstraction involves organizing problems into distinct entities by defining their data and operations.
- Encapsulation involves hiding the internal data structures and offering a well-defined interface for interaction.

Every ADT must provide ways to:
- Add an item.
- Remove an item.
- Find, retrieve, or access an item.
Many more operations are possible:
- Check if the collection is empty.
- Empty the collection.
- Obtain a subset of the collection.

Stacks are data structures that allow access to only the last element added.
They follow a "Last-In, First-Out" (LIFO) principle:
- Push: Adding an element on top of the stack.
- Pop: Removing the top element from the stack.
- Top: Accessing the top element of the stack.
- Make Empty: Clearing the stack.

Queues are data structures that allow access to only the element that has been present the longest.
They follow a "First-In, First-Out" (FIFO) principle:
- Enqueue: Adding elements towards the back of the queue.
- Dequeue: Removing elements from the front of the queue.
- Front: Accessing the element at the front of the queue.
Priority queues are a specific type of queue where elements are removed not by arrival time, but by their assigned priority (highest priority first).

Textbooks:
- Introduction to Data Structures by Ashok N. Kamthane
- Data Structures and Algorithms by A.V. Aho, J.E. Hopcroft, J.D. Ullman
- Data Structures Using C and C++ by Y. Langsam, M.J. Augenstein, A.M. Tenenbaum.

Data: Raw facts and figures that can be turned into useful information.
Data Structure: A way to store and organize data to improve its accessibility and modification.
**Abstract Data Type (ADT)**A mathematical model that defines both the data and the operations that can be performed on it.
Data Structure is a physical implementation of an ADT, using a specific programming language.