Linear Data Structures

• A data structure is a method of organizing related data items.
• The nature of the data items is defined by the problem; this can include integers, characters, or even other data structures.

Linear Data Structures

• Arrays and linked lists are the two most important elementary data structures.
• An array is a sequence of n items of the same data type stored contiguously in memory, accessible by specifying an index value.
• Array indexes are integers, usually between 0 and n − 1 or 1 and n, though some languages allow other ranges or even non-numerical indices.
• Each array element can be accessed in the same constant amount of time, regardless of its location.
• A string is a sequence of characters terminated by a special character which indicates the string’s end.
• Strings composed of zeros and ones are called binary strings or bit strings.
• Common string operations include computing length, comparing strings lexicographically, and concatenating strings.
• A linked list is a sequence of zero or more nodes, each containing data and one or more pointers to other nodes, with a "null" pointer indicating the absence of a successor.
• In a singly linked list, each node contains a single pointer to the next element, except for the last node.
• Accessing a particular node in a linked list requires traversing the pointer chain from the first node.
• Linked lists do not require preliminary memory reservation.
• Insertions and deletions in a linked list are efficient via pointer reconnection.
• A linked list can start with a header node, containing information about the list such as its length, or pointers to the first and last elements.
• A doubly linked list has nodes with pointers to both their successor and predecessor.
• A list is an abstract data structure representing a finite sequence of data items in a linear order.
• Basic operations on a list include searching, inserting, and deleting elements.
• A stack is a list where insertions and deletions occur only at the end, called the top, operating in a "last-in-first-out" (LIFO) manner. Stacks are commonly used to implement recursive algorithms.
• A queue is a list where elements are deleted from the front (dequeue) and added to the rear (enqueue), operating in a "first-in-first-out" (FIFO) manner.
• Queues have numerous applications, including graph algorithms.
• A priority queue selects the item with the highest priority from a changing set of candidates.
• Operations include finding and deleting the largest element, and adding new elements.
• Priority queues can be implemented using arrays or sorted arrays, but a heap data structure provides a more efficient solution.

Graphs

• A graph is a collection of points (vertices or nodes), some connected by line segments (edges or arcs).
• Formally, a graph G = (V, E) is defined by a finite nonempty set V of vertices and a set E of pairs of these vertices called edges.
• Adjacent vertices are connected by an undirected edge (u, v), where the order of vertices does not matter.
• The vertices u and v are endpoints of the edge (u, v) and are incident to this edge; the edge (u, v) is incident to its endpoints u and v.
• In a directed graph, the edge (u, v) is directed from the tail vertex u to the head vertex v.
• Loops, or edges connecting vertices to themselves, are disallowed unless stated otherwise.
• The number of possible edges |E| in an undirected graph with |V| vertices and no loops is: 0 ≤ |E| ≤ |V|(|V| − 1)/2.
• A complete graph has every pair of its vertices connected by an edge, denoted as K|V|.
• A dense graph has relatively few possible edges missing, while a sparse graph has few edges relative to the number of vertices.
• Representation choice (dense or sparse) influences algorithm design and running time.

Graph Representations

• Graphs for computer algorithms are represented in one of two ways: the adjacency matrix and adjacency lists.
• The adjacency matrix of a graph with n vertices is an n × n boolean matrix, where the element in the ith row and jth column is 1 if there is an edge from the ith vertex to the jth vertex, and 0 otherwise.
• The adjacency matrix of an undirected graph is symmetric: A[i, j] = A[j, i] for every 0 ≤ i, j ≤ n − 1.
• The adjacency lists of a graph is a collection of linked lists, one for each vertex, containing all vertices adjacent to that vertex.
• Adjacency lists indicate columns of the adjacency matrix that contain 1's for a given vertex.
• Adjacency list representation uses less space than an adjacency matrix for sparse graphs, but the opposite is true for dense graphs.

Weighted Graphs

• A weighted graph has numbers (weights or costs) assigned to its edges.
• Motivated by real-world applications like finding the shortest path in transportation or communication networks.
• The adjacency matrix of a weighted graph, A[i, j], contains the weight of the edge from the ith to the jth vertex, or a special symbol (e.g., ∞) if no such edge exists.
• Adjacency lists for a weighted graph include both the adjacent vertex and the weight of the corresponding edge.

Paths and Cycles

• A path from vertex u to vertex v is a sequence of adjacent vertices starting with u and ending with v.
• A simple path has distinct vertices.
• The length of a path is the number of vertices in the sequence minus 1 (the number of edges).
• A directed path in a directed graph follows the direction of the edges.
• A graph is connected if there is a path between every pair of its vertices.
• A connected component is a maximal connected subgraph.
• A cycle is a path of positive length that starts and ends at the same vertex without traversing the same edge more than once.
• An acyclic graph has no cycles.

Trees

• A tree (free tree) is a connected acyclic graph.
• A forest is a graph with no cycles but is not necessarily connected; each connected component is a tree.
• The number of edges in a tree is always one less than the number of vertices: |E| = |V| − 1.
• For every two vertices in a tree, there is exactly one simple path from one to the other.
• A rooted tree has a selected vertex considered the root, which is usually depicted on the top (level 0).
• Ancestors of a vertex v include all vertices on the simple path from the root to v.
• The parent of v is the vertex u directly preceding v on the path from the root (if u exists); v is a child of u.
• Siblings share the same parent.
• A leaf has no children, while a parental vertex has at least one child.
• Descendants of v include all vertices for which v is an ancestor.
• The subtree of T rooted at v consists of all descendants of v and the edges connecting them.
• The depth of v is the length of the simple path from the root to v.
• The height of a tree is the length of the longest simple path from the root to a leaf.

Ordered Trees

• An ordered tree is a rooted tree where the children of each vertex are ordered.
• In a tree diagram, children are typically ordered left to right.
• A binary tree is an ordered tree where every vertex has no more than two children, designated as either a left child or a right child; a binary tree may also be empty.
• Common applications include implementation of dictionaries, state-space trees use in analysis of recursive algorithms, efficient management, acces to large datasets and more
• The left (right) subtree of a vertex is the binary tree with its root at the left (right) child of that vertex.
• A binary search tree has the property that for each parental vertex, its value is larger than all values in its left subtree and smaller than all values in its right subtree.
• The height h of a binary tree with n nodes satisfies: ⌊log2 n⌋ ≤ h ≤ n − 1.
• The computer implementation of a binary tree uses nodes containing information and two pointers to the left and right children.
• In the first child–next sibling representation of an ordered tree, the left pointer points to the first child, and the right pointer points to the next sibling.
• This representation transforms an ordered tree into an associated binary tree.

Sets and Dictionaries

• A set is an unordered collection of distinct items called elements.
• Defined by explicitly listing elements or by specifying a property that all elements must satisfy.
• Important set operations include checking membership, finding the union, and finding the intersection.
• Implementation Option 1: If the sets are subsets of a universal set U containing n elements, then each set can be represented by a bit string of size n, called a bit vector.
• Implementation Option 2: Represent a set by a list structure to indicate the set’s elements, only feasible for finite sets.
• A multiset (or bag) is an unordered collection of items that are not necessarily distinct.
• Depending on the application, a set represented by a list might be maintained in a sorted order.
• A dictionary is a data structure that implements searching for a given item, adding a new item, and deleting an item.
• The set union problem involves dynamically partitioning an n-element set into disjoint subsets subject to union and search operations.
• Object-oriented languages such as C++ and Java support abstract data types by means of classes.