Linked Lists in Programming

Arrays are quite useful in all programming languages. However, they also have some limitations. They require creating a new array with bigger size and copying the existing elements from the old array to the new one when the capacity of an array is overrun. Additionally, they have to shift some elements in an array when a new element is inserted because memory of an array is sequentially allocated. Such limitations can be overcome by dynamic structures, such as linked lists.It is not necessary to know the size of a list when it is created, so it is treated as a dynamic data structure. Rather than allocate memory for all elements when a list is initialized, memory is allocated for each node on demand when it is inserted. The space efficiency of lists is better than arrays because there is no vacant memory in lists.Memory allocation of a list is not continuous because nodes are inserted dynamically and their memory is not allocated at the same time. It costs O(n) time to get the ith node in a list since it has to traverse nodes one by one starting from the head node. It only takes O(1) time to get the ith element in an array. Therefore, time efficiency to search lists is not as good as for arrays.

Linked lists are the most frequently met data structures during interviews. It only takes about 20 lines of code to create a list, insert a node into a list, or delete a node from a list. Compared to other complex data structures, such as hash tables and graphs, lists are more suitable for interviews due to their moderate code size. Additionally, lots of pointer operations are required to handle a list. Candidates without qualified programming abilities cannot implement complete and robust code related to lists. Moreover, lists are also flexible and challenging interview questions can be constructed with them. Therefore, many interviewers like questions related to lists.

Most lists met during interviews are single-linked lists, where each node has a link to its successor. For example, “Print a List from Tail to Head”, “Delete a Node from a List in O(1) Time”, “kth Node from the End”, “Reverse Lists”, and “First Intersection Node of Two Lists" are all about single-linked lists.
Not only are single-linked lists popular for interviews, but other types of lists are also frequently met:

• Usually the tail node in a single-linked list does not have a successor. If every node in a finite list has a successor, a loop is formed. The section Loop in List discusses lists with loops.
  
• If there is also a link to a predecessor besides a link to a successor in each node of a list, it is a double-linked list. The interview question “Binary Search Trees and Double-Linked Lists” is in this category.
  
• A complex list is composed if each node has a link to any other node (including the node itself). Please refer to the interview question “Clone Complex Lists” for more details on the complex list.
  

www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community