Data Structures & Algorithms - Linear Data Structures

Comprehensive practice flashcards covering Data Structures and Algorithms basics, linear data structures, and detailed operations of Linked Lists, Stacks, and Queues.

What is a Data Structure?

A way of organizing and storing data in memory so it can be used efficiently.

What are Algorithms?

Step-by-step methods used to solve problems.

What characterizes a Linear Data Structure?

It stores data one after another in a sequence, arranged in a straight line, making it easy to traverse and implement because computer memory is also arranged linearly.

What are the four main types of linear data structures mentioned?

1. Array, 2. Linked List, 3. Stack, 4. Queue.

How does an Array store data and what is a drawback regarding its size?

It stores items in a single line of memory where each item has a position called an index; its size is usually fixed.

What are the two parts of a node in a Linked List?

1. Data and 2. Address of the next node.

According to the transcript, why is a Linked List efficient in terms of memory management?

It has dynamic size (grows/shrinks at runtime), results in no wasted memory compared to fixed arrays, allows for memory allocation at runtime, and can utilize scattered (non-continuous) memory locations.

What is the role of the head pointer in a Linked List?

It is the starting point that stores the address of the first node, allowing for traversal and control of all operations like insert, delete, or search.

What occurs if the head pointer of a Linked List is missing?

The entire linked list is lost, nodes become unreachable (leading to a memory leak), and no operations (insert, delete, search) can be performed.

What are the characteristics of a Singly Linked List?

It is the simplest type where each node has data and the address of the next node; it moves in one direction only (forward) and the last node points to NULL.

How does a Doubly Linked List differ from a Singly Linked List?

A Doubly Linked List allows movement in both directions because each node contains the address of both the next node and the previous node.

What is unique about a Circular Linked List?

The last node connects back to the first node, forming a circle with no NULL at the end.

What is the definition of Traversal in a Linked List?

Visiting or accessing all elements of a linked list one by one in order, starting from the head and following pointers until the last node where the pointer is NULL.

What is the time complexity of traversal in a Linked List?

$O(n)$, where $n$ is the number of nodes, meaning time grows linearly with the number of elements.

Where can a new node be inserted in a Linked List?

At the beginning (head), at the end (tail), or at a specific position (middle).

What are the steps to delete a node from a Linked List?

1. Find the target node, 2. Find the previous node connected to it, 3. Change the pointer so the previous node points to the next node (skipping the unwanted node).

What are the common types of searching in a Linked List?

1. Linear Search (Sequential Search), where nodes are checked one by one from the head; 2. Search by Position, where the program moves node by node until a specific position number is reached.

What is the Best-case and Worst-case time complexity for searching in a Linked List?

Best case is $O(1)$ (item found at the first node); Worst case is $O(n)$ (item found at the last node or not found).

What rule does a Stack follow and what are its primary operations?

It follows the LIFO (Last In, First Out) principle; operations are Push (adding an item) and Pop (removing an item).

What rule does a Queue follow and what are its primary operations?

It follows the FIFO (First In, First Out) principle; operations are Enqueue (adding an item) and Dequeue (removing an item).