DATA STRUC MIDTERM

Linear Data Structure

A data structure where elements are organized sequentially in a linear order.

Array

A fixed

Array Index

A number used to identify the position of an element in an array.

One

Dimensional Array

Two

Dimensional Array

Array Declaration

The process of defining an array variable using a data type and array name.

Array Declaration Syntax

type[] arrayName;

Array Creation

Creating an array using the new keyword and specifying its size.

Array Element

A single value stored at a specific index of an array.

Array Access

Retrieving an array element using its index.

Array Element Modification

Changing an array element by assigning a new value to its index.

Array Length

The number of elements an array can contain, accessed using the .length property.

Static Array

An array with a fixed size that cannot be changed after creation.

Static Array Size

The size of a static array is determined when the array is created.

Static Array Access

Static array elements can be accessed in constant time.

Static Array Usage

Useful when the number of elements is known beforehand.

Dynamic Array

An array that can grow or shrink during runtime.

Dynamic Array in Java

ArrayList is used to create resizable arrays in Java.

ArrayList

A Java collection that can dynamically grow and shrink.

ArrayList Add

The add() method inserts an element into an ArrayList.

Static Array Example

int[] numbers = new int[6];

Dynamic Array Example

ArrayList<Integer> numbers = new ArrayList<>();

Linked List

A chain of nodes where each node contains data and a reference to another node.

Node

An element of a linked list that contains data and one or more references.

Singly Linked List

A linked list where each node contains data and a reference to the next node.

Singly Linked List Node

A node containing data and a next reference.

Next Pointer

A reference that points to the next node in a linked list.

Null in Singly Linked List

The next reference of the last node is null.

Doubly Linked List

A linked list where each node has references to both previous and next nodes.

Previous Pointer

A reference that points to the previous node in a doubly linked list.

Doubly Linked List Node

A node containing data, a previous reference, and a next reference.

Head

A reference to the first node of a linked list.

Tail

A reference to the last node of a linked list.

Forward Traversal

Traversing a doubly linked list from head to tail using next.

Backward Traversal

Traversing a doubly linked list from tail to head using prev.

Linked List Traversal

Visiting each node one by one to read, display, or process its data.

Linked List Insertion

Adding a new node to a linked list.

Linked List Deletion

Removing an existing node from a linked list.

Linked List Search

Finding a node containing a specific value.

Linked List Sort

Arranging linked list values in ascending or descending order.

Search Process

Start at head, compare the value, move to next, and repeat until found or null.

Linked List Random Access

Linked lists do not support random access like arrays.

Collections.sort()

A Java method used to sort the values of a built

Tree

A hierarchical data structure used to represent relationships between elements.

Binary Tree

A tree where each parent node can have at most two children.

Root

The topmost node of a tree.

Parent Node

A node that has one or more child nodes.

Child Node

A node connected below another node in a tree.

Left Child

The child node located on the left side of a binary tree node.

Right Child

The child node located on the right side of a binary tree node.

Leaf Node

A node that has no children.

Binary Tree Node Fields

Data, pointer to the left child, and pointer to the right child.

Tree Traversal

The process of visiting every node in a tree exactly once in a specific order.

Breadth

First Traversal

Level Order Traversal

Another name for Breadth

Queue in Tree Traversal

A queue is used to implement Breadth

Depth

First Traversal

Inorder Traversal

Visits Left subtree, Root, then Right subtree.

Preorder Traversal

Visits Root, Left subtree, then Right subtree.

Postorder Traversal

Visits Left subtree, Right subtree, then Root.

Inorder BST Result

Inorder traversal of a BST retrieves values in sorted order.

Preorder Use

Commonly used for duplicating trees or evaluating prefix expressions.

Postorder Use

Useful for deleting trees or evaluating postfix expressions.

Level Order Example

For the sample tree, the order is 10, 5, 15, 2, 7, 12.

Binary Search Tree

An ordered binary tree used for retrieving, sorting, and searching data.

BST Left Rule

All nodes in the left subtree contain keys less than the node's key.

BST Right Rule

All nodes in the right subtree contain keys greater than the node's key.

BST Subtree Rule

Both the left and right subtrees must also be valid BSTs.

BST Duplicate Rule

The handout specifies that BSTs do not allow duplicate nodes.

BST Unique Key

Every node in the BST has a unique key.

BST Ordering Rule

Left subtree < Node < Right subtree.

BST Search Direction

Smaller values go left and greater values go right.

Binary Tree vs BST

A binary tree has no required ordering rule, while a BST follows strict ordering.

AVL Tree

A self

AVL Balance Factor

The difference between the height of the left subtree and right subtree.

Balance Factor Formula

Balance Factor = Height of Left Subtree

AVL Balance Factor +1

The left subtree is taller by one.

AVL Balance Factor 0

The left and right subtrees have equal height.

AVL Balance Factor

1

AVL Unbalanced Factor

A balance factor beyond

AVL Rotation

A tree restructuring operation used to restore AVL balance.

LL Rotation

Left

RR Rotation

Right

LR Rotation

Left

RL Rotation

Right

LL Pattern

Insertion occurs in the left subtree of the left child.

RR Pattern

Insertion occurs in the right subtree of the right child.

LR Pattern

Insertion occurs in the right subtree of the left child.

RL Pattern

Insertion occurs in the left subtree of the right child.

LL Memory Trick

LL means Right Rotation.

RR Memory Trick

RR means Left Rotation.

LR Memory Trick

LR means Left then Right.

RL Memory Trick

RL means Right then Left.

Hierarchical Data

Data organized according to relationships between levels or entities.

File System Trees

Trees represent directories, subdirectories, and files.

Organizational Chart

A hierarchical structure commonly represented using trees.

DOM Tree

The tree structure used to represent nested HTML or XML elements.

BST Applications

Searching, sorting, insertion, and deletion of data.

AVL Applications

Maintaining balanced height for consistent efficient operations.

Red

Black Tree