LINKED LISTS

Question 1

Define and illustrate a linked list

Answer 1

Linked list is simply a chain of self-referential data nodes.
*See notes for pic

Question 2

What is a list node

Answer 2

The list node is a simple self-referential structure that stores an item of
data, and a reference to the next item.

Question 3

Describe the end and start of a linked list

Answer 3

• The end of the list is defined by a null next reference.
• The start (or head) of the list is contained in a header class, which also
encapsulates all the list’s functionality. This helps the linked list become
an independent, cohesive package.

Question 4

What are the advantages of linked lists

Answer 4

• Size of linked lists is not fixed, they can expand and
shrink during run time.
• Insertion and Deletion Operations are fast and easier in
Linked Lists.
• Memory allocation is done during run-time (no need to
allocate any fixed memory).
• Data Structures like Stacks, Queues, and trees can
be easily implemented using Linked list.

Question 5

What is the difference between singly linked lists and arrays

Answer 5

• Singly Linked Lists store elements in linear order, accessible with links (can’t be random) while arrays store elements in linear order but accessible with an index (can be random)
• Singly linked lists do not have fixed sizes while arrays have fixed sizes

-In arrays data elements are stored in contiguous locations in
memory while in SLLs new elements can be stored anywhere and a
reference is created for the new element using
pointers.

-Array- Memory is allocated during the compile time (Static
memory allocation). While SLL- Memory is allocated during the run-time (Dynamic
memory allocation)

Question 6

Describe a doubly linked list

Answer 6

• Each node contains a value, a link to its successor (if any), and a link to its predecessor (if any)
• The header points to the first node in the list and to
the last node in the list (or contains null links if the list
is empty)

Question 7

What are the advantages of doubly linked lists over singly linked lists

Answer 7

– Can be traversed in either direction (may be essential for some programs)
– Some operations, such as deletion and inserting before a node, become easier.

Question 8

What are the disadvantages of doubly linked lists over singly linked lists

Answer 8

– Requires more space
– List manipulations are slower (because more links must be changed)
– Greater chance of having bugs (because more links must be manipulated)

Question 9

What are the Advantages of Circular Linked List

Answer 9

We can go to any node from any node in the Circular linked list which was not possible in the singly linked list
if we reached the last node.
• Easily we can go to head from the last node
• In a circular list, any node can be starting point means
we can traverse each node from any point.

Question 10

What are the disadvantages of Circular Linked List

Answer 10

• If not handled proper validation then code may go in an infinite loop.
• Not easy to reverse a circular linked list.
• For the implementation perspective to insert at the beginning we have to traverse the complete list to find the last node.
• Harder to find the end of the list and loop control.

Question 11

Explain any TWO challenges of an array data structure, which have been addressed by a LinkedList

Answer 11

Better use of Memory:
From a memory allocation point of view, linked lists are more efficient than arrays. Unlike arrays, the size for a linked list is not pre-defined, allowing the linked list to increase or decrease in size as the program runs.

Fast Insertion/Deletion Time