Linked Lists

Question 1

What is a linked list?

Answer 1

A linear data structure where elements are stored in nodes, and each node points to the next.

Question 2

What are the main types of linked lists?

Answer 2

Singly linked lists, doubly linked lists, and circular linked lists.

Question 3

What is a singly linked list?

Answer 3

A linked list where each node points to the next node, and the last node points to null.

Question 4

What is a doubly linked list?

Answer 4

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

Question 5

What is a circular linked list?

Answer 5

A linked list where the last node points back to the head node.

Question 6

What is the head of a linked list?

Answer 6

The first node in the list.

Question 7

What is the tail of a linked list?

Answer 7

The last node in the list.

Question 8

How do you insert at the beginning of a singly linked list?

Answer 8

Create a new node and point it to the current head, then update head to the new node.

Question 9

What is the time complexity of inserting at the head of a linked list?

Answer 9

O(1)

Question 10

How do you insert at the end of a singly linked list?

Answer 10

Traverse to the last node, then set its next pointer to a new node.

Question 11

What is the time complexity of inserting at the end of a singly linked list?

Answer 11

O(n)

Question 12

How do you delete the head node in a singly linked list?

Answer 12

Update the head to point to the next node.

Question 13

How do you delete the tail node in a singly linked list?

Answer 13

Traverse to the second-last node and set its next pointer to null.

Question 14

What is the time complexity of searching in a linked list?

Answer 14

O(n)

Question 15

What is the space complexity of a linked list with n nodes?

Answer 15

O(n)

Question 16

How does a linked list differ from an array?

Answer 16

Linked lists use dynamic memory and support efficient insertion/deletion; arrays allow constant-time access.

Question 17

What is a node in a linked list?

Answer 17

A basic unit containing data and one or more pointers.

Question 18

What are common operations on linked lists?

Answer 18

Insert, delete, search, traverse, reverse.

Question 19

How do you reverse a singly linked list?

Answer 19

Iterate through the list and rewire each node to point to the previous node.

Question 20

What is a dummy head node?

Answer 20

A placeholder node at the beginning of a list to simplify edge cases.

Question 21

What is the advantage of a dummy node?

Answer 21

Simplifies insertion and deletion logic, especially at the head.

Question 22

What is a null pointer in linked lists?

Answer 22

A special value indicating the end of the list.

Question 23

Can a linked list have cycles?

Answer 23

Yes, if a node’s next pointer links back to a previous node.

Question 24

How do you detect a cycle in a linked list?

Answer 24

Use Floyd’s Cycle Detection Algorithm (Tortoise and Hare).

Question 25

What is the time complexity of cycle detection using Floyd’s algorithm?

Answer 25

O(n)

Question 26

What is the space complexity of Floyd’s cycle detection algorithm?

Answer 26

O(1)

Question 27

What is a sentinel node?

Answer 27

Another name for a dummy node used as a placeholder.

Question 28

What is the benefit of a circular linked list?

Answer 28

Allows continuous traversal from tail to head.

Question 29

What is a use case for a doubly linked list?

Answer 29

Efficient backward traversal or deletion without needing to traverse the list.

Question 30

What is the time complexity of inserting at a known position in a doubly linked list?

Answer 30

O(1)

Question 31

What is the time complexity of inserting at a known position in a singly linked list?

Answer 31

O(1) if the node is known, otherwise O(n)

Question 32

How is memory allocated in linked lists?

Answer 32

Each node is allocated dynamically on the heap.

Question 33

What is a memory leak in the context of linked lists?

Answer 33

Forgetting to free memory for removed nodes.

Question 34

How do you traverse a linked list?

Answer 34

Start from the head and follow next pointers until null.

Question 35

How do you find the length of a linked list?

Answer 35

Traverse the list, incrementing a counter until reaching null.

Question 36

How do you merge two sorted linked lists?

Answer 36

Use a two-pointer approach to build a new sorted list.

Question 37

How do you implement a stack with a linked list?

Answer 37

Insert and delete from the head of the list.

Question 38

How do you implement a queue with a linked list?

Answer 38

Insert at the tail and delete from the head.

Question 39

What is the advantage of a linked list over an array in dynamic scenarios?

Answer 39

Linked lists can grow and shrink in size without reallocating memory.

Question 40

What is the main disadvantage of linked lists?

Answer 40

No constant-time random access; more memory usage due to pointers.

Question 41

What causes segmentation faults in linked lists?

Answer 41

Accessing or modifying memory through an invalid or null pointer.

Question 42

How do you remove duplicates from an unsorted linked list?

Answer 42

Use a hash set to track seen values.

Question 43

What is a common interview question involving linked lists?

Answer 43

Detect and remove cycles, or find the intersection point of two lists.

Question 44

How do you find the middle of a linked list?

Answer 44

Use two pointers: one moves twice as fast as the other.

Question 45

What is the time complexity of finding the middle element in a linked list?

Answer 45

O(n)

Question 46

How do you find the nth node from the end?

Answer 46

Use two pointers with a gap of n between them.

Question 47

Can you sort a linked list?

Answer 47

Yes, using merge sort which works efficiently with linked lists.

Question 48

What is the time complexity of merge sort on linked lists?

Answer 48

O(n log n)

Question 49

What is the benefit of using merge sort on a linked list over quicksort?

Answer 49

No random access is needed, and merge sort is stable.

Question 50

What is a circular doubly linked list?

Answer 50

A doubly linked list where the tail connects back to the head and vice versa.

Question 51

What are sentinel values used for in linked lists?

Answer 51

To simplify boundary conditions during traversal or modification.