Linked Lists

Question 1

Define Linked List

Answer 1

A linked list is a linear data structure where each element is a separate object. Each element (we will call it a node) of a list is comprising of two items - the data and a reference (pointer) to the next node.

The last node has a reference to null. The entry point into a linked list is called the head of the list.

It should be noted that the head is not a separate node, but a reference to the first node. If the list is empty then the head is a null reference.

Question 2

Name Advantages of Linked Lists

Answer 2

• Linked Lists are Dynamic Data Structure - they can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.
• Insertion and Deletion are simple to implement - Unlike an array, here we don’t have to shift elements after insertion or deletion of an element. In the linked list, we just have to update the address present in the next pointer of a node.
• Efficient Memory Allocation/No Memory Wastage - In the case of an array, there is a lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements are wasted. There is no such problem in the linked list as memory is allocated only when required.

Question 3

What is a cycle/loop in the singly-linked list?

Answer 3

A cycle/loop occurs when a node’s next points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

Question 4

What are some types of Linked Lists?

Answer 4

• A singly linked list
• A doubly linked list is a list that has two references, one to the next node and another to the previous node.
• A multiply linked list - each node contains two or more link fields, each field being used to connect the same set of data records in a different order of the same set(e.g., by name, by department, by date of birth, etc.).
• A circular linked list - where the last node of the list points back to the first node (or the head) of the list.

Question 5

What is the Time Complexity of Linked List Operations?

Answer 5

• A linked list can typically only be accessed via its head node. From there you can only traverse from node to node until you reach the node you seek. Thus access is O(n).
• Searching for a given value in a linked list similarly requires traversing all the elements until you find that value. Thus the search is O(n).
• Inserting into a linked list requires re-pointing the previous node (the node before the insertion point) to the inserted node, and pointing the newly inserted node to the next node. Thus insertion is O(1).
• Deleting from a linked list requires re-pointing the previous node (the node before the deleted node) to the next node (the node after the deleted node). Thus deletion is O(1).

Question 6

Name some Disadvantages of Linked Lists?

Answer 6

• They use more memory than arrays because of the storage used by their pointers.
• Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly-linked lists are cumbersome to navigate backward and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.
• Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
• Random access has linear time.
• Nodes are stored incontiguously (none OR poor cache locality), greatly increasing the time required to access individual elements within the list, especially with a CPU cache.
• If the link to the list’s node is accidentally destroyed then the chances of data loss after the destruction point is huge. Data recovery is not possible.
• Search is linear versus logarithmic for sorted arrays and binary search trees.
• A different amount of time is required to access each element.
• Not easy to sort the elements stored in the linear linked list.

Question 7

Under what circumstances are Linked Lists useful?

Answer 7

Linked lists are very useful when you need :

• to do a lot of insertions and removals, but not too much searching, on a list of arbitrary (unknown at compile-time) lengths.
• splitting and joining (bidirectionally-linked) lists is very efficient.
• You can also combine linked lists - e.g. tree structures can be implemented as “vertical” linked lists (parent/child relationships) connecting together horizontal linked lists (siblings).

Using an array-based list for these purposes has severe limitations:

• Adding a new item means the array must be reallocated (or you must allocate more space than you need to allow for future growth and reduce the number of reallocations)
• Removing items leaves wasted space or requires a reallocation
• inserting items anywhere except the end involves (possibly reallocating and) copying lots of the data up one position

Question 8

How do you Implement Linked Lists Using Stacks?

Answer 8

You can simulate a linked list by using two stacks. One stack is the “list,” and the other is used for temporary storage.

• To add an item at the head, simply push the item onto the stack.
• To remove from the head, pop from the stack.
• To insert into the middle somewhere, pop items from the “list” stack and push them onto the temporary stack until you get to your insertion point. Push the new item onto the “list” stack, then pop from the temporary stack and push back onto the “list” stack. Deletion of an arbitrary node is similar.

This isn’t terribly efficient, by the way, but it would in fact work.