Quiz: Data structures linked lists

What is a linked list?

A data structure consisting of nodes, where each node contains data and a reference (link) to the next node.

True or False: Linked lists store elements in contiguous memory locations.

False. Linked lists do not require contiguous memory; nodes can be scattered throughout memory.

Node structure components?

- Data - Pointer to next node

Advantages of linked lists over arrays?

- Dynamic size - Efficient insertions/deletions

What is a head in a linked list?

The first node in a linked list, which serves as the entry point to access the list.

Fill in the blank: A linked list can be traversed using _____ pointers.

next

Characteristics of linked lists?

- Non-contiguous memory - Dynamic size - Flexible data insertion

What is a tail in a linked list?

The last node of a linked list, which points to null, indicating the end of the list.

Cause of linked list advantages?

The ability to allocate memory dynamically allows for efficient handling of varying data sizes.

True or False: Linked lists can only store homogeneous data types.

False. Linked lists can store heterogeneous data types, depending on the design.

Example of a simple linked list?

Head -> 5 -> 10 -> 15 -> null

What does 'null' signify in a linked list?

It indicates that a node does not link to another node, usually marking the end of the list.

Difference between linked list and array?

Arrays have fixed size; linked lists can grow or shrink dynamically.

What is a circular linked list?

A linked list where the last node points back to the first node, forming a circle.

Fill in the blank: Each node in a linked list can hold _____.

data and a pointer

Advantages of linked lists in insertion?

Insertions can be performed without shifting other elements, making it efficient.

Insertion in a linked list?

Adding a new node to the list. - At the head - At the tail - At a specific position

True or False: Deletion can only occur at the head.

False. Deletion can occur at: - Head - Tail - Any position

How to insert a node at the head?

1. Create a new node. 2. Point new node's next to current head. 3. Update head to new node.

What is tail insertion?

Adding a node to the end of the linked list. - Traverse to end - Update last node's next to new node

Fill in the blank: Deleting a node requires _____.

Updating the previous node's next pointer

Comparison: Insertion vs. Deletion

Insertion: Adds a node. Deletion: Removes a node.

How to delete the last node?

1. Traverse to second to last node. 2. Set its next to null.

What happens during middle insertion?

1. Traverse to the desired position. 2. Adjust pointers of surrounding nodes.

True or False: Only one pointer is required for deletion.

False. You need a pointer to the node to delete and one to its previous.

What is a common mistake in deletion?

Forgetting to update the previous node's pointer.

Cause → Effect: Inserting at a specific position.

Cause: Traversing the list. Effect: New node is added at the desired position.

How to handle deletion when the list is empty?

Simply return, as there are no nodes to delete.

What is the time complexity of insertion?

O(1) for head, O(n) for tail or specific position.

What is the time complexity of deletion?

O(1) for head, O(n) for tail or specific node.

Fill in the blank: Insertions can lead to _____.

Increased memory usage.

Example: Insert 5 at the head of [3, 4].

[5, 3, 4] after insertion.

Singly Linked List →

A data structure consisting of nodes where each node points to the next node. Each node contains data and a single link to the next node.

Doubly Linked List →

A linked list where each node contains a link to both the next and the previous node, allowing traversal in both directions.

True or False: Circular linked lists can be singly or doubly linked.

True. Circular linked lists can have either singly or doubly linked structures where the last node points back to the first.

What is a Circular Linked List?

A linked list where the last node points back to the first node, forming a circle. It can be singly or doubly linked.

Advantages of Doubly Linked Lists

- Easier to traverse backwards - More flexible insertion and deletion - Efficient forward and backward traversal

Fill in the blank: A ______ linked list allows traversal in both directions.

Doubly

Difference between Singly and Doubly Linked Lists?

- Singly: One link per node - Doubly: Two links per node

What does a Node contain in a Linked List?

Typically contains data and a pointer (or pointers) to other nodes, depending on the type of linked list.

True or False: All linked lists must have a tail.

False. A linked list can be empty or have just one node without a distinct tail.

What is a Multilinked List?

A linked list where each node can point to multiple nodes, forming more complex relationships, often used in applications like adjacency lists.

Example of Singly Linked List

Node A → Node B → Node C. Each node points to the next, with Node C having no forward link.

Key Feature of Circular Linked Lists

The last node links back to the first node, creating a continuous loop.

What is a Header Node?

A special node used in linked lists that acts as a placeholder or sentinel, simplifying operations like insertion and deletion.

True or False: Singly linked lists are more memory efficient than doubly linked lists.

True. Singly linked lists use less memory as they store only one pointer per node.

Singly Linked List: Traversal Complexity

Traversal is $\displaystyle O(n)$ time complexity, where $\displaystyle n$ is the number of nodes.

Example of a Doubly Linked List

Node A ⇄ Node B ⇄ Node C. Each node has pointers to both the previous and next nodes.

Real-time gaming applications

Linked lists efficiently manage dynamic game entities, such as player actions and game state updates.

True or False: Linked lists are faster than arrays for random access.

False. Linked lists have O(n) access time, while arrays have O(1) due to contiguous memory.

Fill in the blank: Linked lists are ideal for __________ data where size fluctuates.

dynamic

How do linked lists improve memory usage?

They allocate memory as needed, reducing waste compared to fixed-size arrays.

Example of a linked list in real-world applications:

Music playlists, where each song node links to the next, allowing easy additions and deletions.

Linked lists vs. Arrays: Insertion speed?

Linked lists allow O(1) insertions at known positions, while arrays require O(n).

Why use linked lists in web browsers?

They maintain history stacks for back and forward navigation, allowing easy insertion and deletion of pages.

True or False: Linked lists can implement queues and stacks.

True. They can represent both with efficient operations.

What is a significant advantage for managing memory in linked lists?

They use pointers to link elements, minimizing the need for contiguous memory allocation.

Linked lists are used in __________ for dynamic data management.

operating systems

How do linked lists support undo features in applications?

Each action can point to the previous state, allowing easy backtracking.

Comparative traversal: Linked lists vs. Arrays.

Linked lists require O(n) for traversal, while arrays have O(n) but are faster due to locality.

What common data structure uses linked lists for implementation?

Hash tables, where linked lists manage collisions.

True or False: Linked lists are unsuitable for implementing priority queues.

False. They can efficiently manage priority queues with sorted insertion.

How can linked lists manage real-time data streams?

By appending new data easily without reallocating, maintaining a continuous flow.

Example use case: Implementing a browser's bookmarks.

A linked list allows for easy addition, deletion, and rearrangement of bookmarks.