liveBookmanning.com

What you will learn in Grokking Data Structures

by Marcello La Rocca

Read it on liveBook Get the book at manning.com

Chapter by chapter

Concepts explained in this book

• linked listA linked list is a collection of nodes connected by links, allowing elements to be inserted or removed without requiring contiguous storage.
• queueA queue is a data structure in which elements are retrieved in the same order in which they were added.
• data structureA data structure is an organized representation for storing data that defines relationships among elements and the operations and access constraints applicable to them.
• fixed-size arrayA static array is an array whose size is fixed when it is created and whose storage is allocated for that fixed number of elements.
• performancePerformance is the measured efficiency of a system, including factors such as execution time and resource consumption.
• nodeA vertex is a node in a graph that represents an entity or endpoint of relationships.
• arrayAn array is a data structure that stores elements in an ordered, typically contiguous sequence accessed by index.
• MapA dictionary is an associative data structure that maps keys to values and supports operations such as lookup, insertion, and deletion by key.
• stackStack is the book's class that implements a stack interface by wrapping an underlying linked list.
• vectorA dynamic array is an array-like data structure whose storage can grow or shrink as elements are added or removed.
• binary search treeA binary search tree is a binary tree whose node values obey an ordering rule in which left-subtree values are less than or equal to a node value and right-subtree values are greater.
• abstract data typeAn abstract data type is a specification of the operations and behavior of a data type independent of its implementation.
• heapA binary heap is a heap represented as a binary, almost complete tree in which each node satisfies the heap ordering property relative to its children.
• edgeA tree link is a connection from one tree node to another tree node, typically representing a parent-child relationship.
• sorted listA sorted list is a list whose elements are maintained in a defined order.
• insert methodAn insert method is an operation that adds an element to a data structure while preserving its required representation constraints.
• array resizingArray resizing is the process of changing an array's allocated storage by replacing it with an array of a different size and transferring elements.
• indexingAn array index is the position used to identify an element within an array.
• bagBag is the book's class that wraps an underlying linked list and exposes operations for inserting and traversing bag elements.
• similarity searchSearch is an operation that determines whether a target value occurs in a collection and identifies its position.
• traversalArray traversal is the process of visiting the elements of an array, typically to inspect or process their values.
• delete methodA delete method is an operation that removes an element from a data structure.
• insertInsertion is the operation of adding a new element to a collection while placing it in the position required by the collection's ordering.
• enqueueEnqueue is the queue operation that adds an element to the insertion end of the queue.
• dequeueDequeue is a queue operation that removes and returns the least recently added element from the front of the queue.
• priority queueA priority queue is a data structure that retrieves elements according to their priority rather than solely by insertion order.
• doubly linked listA doubly linked list is a linked list in which each node contains links to both its previous and next nodes, supporting traversal in both directions.
• breadth-first searchBreadth-first search explores a graph level by level, visiting vertices in order of their distance from a starting vertex.
• graphA graph is a data structure consisting of vertices and edges representing entities and relationships between them.
• hash functionA hash function is a function that maps input data to a bounded hash value used to compute or organize lookup keys.
• binary searchBinary search locates an item in an ordered sequence by repeatedly eliminating the half of the remaining search range that cannot contain it.
• contractAn API is a defined set of programmatic operations and interaction rules exposed by a software component.
• predecessorAn in-order predecessor is the greatest node value that precedes a specified node value in the sorted order of a binary search tree.
• circular queueA circular queue is a queue implemented over storage in which the front and rear positions wrap around from the end to the beginning.
• virtual indexA virtual index is a logical position in a circular array that is mapped to a physical array position, typically using modular arithmetic.
• leaf nodeA leaf is a tree node that has no child links.
• cycleA cycle is a path in a graph that starts and ends at the same vertex.
• tree heightTree height is the length of the longest path from a tree's root to any leaf, measured in edges or levels according to the chosen convention.
• linear searchLinear search examines the elements of a sequence one by one, typically from one end to the other, until the target is found or the sequence is exhausted.
• task prioritizationPriority is an ordering value or criterion that determines which element should be placed at the root or retrieved first from a heap.
• amortized analysisAmortized analysis establishes a bound on the combined cost of a sequence of operations by distributing occasional expensive operations across the sequence.
• complete binary treeAn almost complete binary tree is a binary tree whose levels are full except possibly the last, which is filled from left to right.
• maximumA maximum value is the greatest element in a collection under the relevant ordering.
• capacityArray capacity is the maximum number of elements allocated for an array.
• chainingChaining is a hash-table conflict-resolution technique that stores multiple entries mapped to the same index in a linked or otherwise grouped collection.
• direct-access tableA direct-access table is an array-based data structure that stores each element at an array position determined directly by its key or associated index.
• keyA key is an identifier associated with a value that determines how the value is located in an associative data structure.
• subtreeA subtree is a tree consisting of a node and all of its descendants within a larger tree.
• growth rateA growth function describes how a quantity changes as the size of its input increases.
• topA priority queue top method is an operation that removes and returns the element with the highest priority.
• referenceA reference is a language-level value that identifies or provides access to an object or memory location.
• containerA container is a data structure that groups multiple data elements as a single entity and supports operations such as access, insertion, deletion, and search.
• linear time complexityLinear growth is growth proportional to input size.
• treeA tree is a hierarchical data structure whose elements are connected by parent-child relationships without cycles.
• unsorted arrayAn unsorted array is an array whose elements are not maintained in a defined sorted order and whose occupied prefix is tracked separately from its unused storage.
• tailThe tail is the reference or position identifying the last node of a linked list.
• undirected graphAn undirected graph is a graph whose edges represent symmetric relationships without an orientation from one vertex to another.
• depth-first searchDepth-first search is a graph traversal algorithm that explores a path as deeply as possible before backtracking.
• linear queueA linear queue is a queue implementation whose front and rear positions advance linearly through its underlying array without wrapping around.
• rearThe rear is the end of a queue at which new elements are added.
• acyclic graphAn acyclic graph is a graph that contains no cycles.
• tradeoffA trade-off is a compromise in which improving one consideration or property requires accepting a disadvantage in another.
• adjacency listAn adjacency list is a graph representation that associates each source vertex with a collection of its outgoing edges or destination vertices.
• open addressingOpen addressing is a hash-table collision-resolution technique that stores entries directly in the table array and probes alternative positions when collisions occur.
• private memberA private attribute is an object attribute intended to be accessed only within the implementation that defines it.
• listA list is a Python sequence type that stores an ordered collection of elements and supports dynamic resizing and heterogeneous element types.
• circular linked listA circular linked list is a linked list whose final node links back to a node in the list, forming a cycle rather than ending at a null reference.
• head pointerA head reference is a reference identifying the first node of a linked list.
• ancestorAn ancestor is a node that lies above another node on a tree path toward the root.
• multiplication methodThe multiplication method is a hashing technique that multiplies a key by a constant, extracts the fractional part, and scales it by the table size to produce an index.
• heapifyA heapify method is an operation that transforms an array of elements into a heap.
• extra memoryExtra space is memory used by an algorithm beyond the memory already occupied by the data structure it operates on.
• exponentialExponential growth is growth proportional to a fixed base raised to a power that increases with input size.
• linearithmic functionLinearithmic growth is growth proportional to the product of input size and its logarithm.
• successorA tree successor is the node whose value immediately follows a given node's value in the tree's ordering.
• indexing functionAn indexing function is a function that maps a key or element to the array index where its associated value is stored.
• compositionComposition is a design technique that builds an object from instances of other objects rather than deriving it through inheritance.
• directed graphA directed graph is a graph whose edges have orientations that distinguish a source vertex from a destination vertex.
• logarithmA logarithmic function grows proportionally to the logarithm of its input and therefore increases very slowly as input size grows.
• modulo arithmeticModular arithmetic is arithmetic in which values are considered equivalent when they have the same remainder under a specified modulus.
• remainder operationThe modulo operator computes the remainder after integer division.
• internal nodeAn internal node is a tree node that has at least one child.
• encapsulationEncapsulation is the bundling of data with the operations that manage it while restricting direct access to the data's internal representation.
• pathA path is a sequence of connected nodes in a graph from one vertex to another.
• peekA peek operation returns the top element of a stack without removing it or changing the stack's structure.
• min-heapA min-heap is a heap in which every parent has a value no larger than its children, so the root contains the smallest element.
• popA pop method is a stack operation that removes and returns the most recently added element.
• RAM modelA random-access machine is an abstract computation model with a single processor, uniform random-access memory, and basic instructions that take constant time.
• pushA push method is a stack operation that adds an element to the top of the stack.
• connected componentA connected component is a maximal subgraph in which every pair of vertices is connected by a path.
• hash chainA hash chain is a linked list attached to a hash-table bucket that stores entries mapped to that bucket.
• self-balancing binary search treeA balanced binary search tree is a binary search tree whose height is constrained to remain logarithmic in the number of elements.
• quadratic time complexityQuadratic growth is growth proportional to the square of input size.

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.