Linked List vs Array vs Both! Learning DS Practice Questions

Question: Suppose you’re building an app for restaurants to take customer orders. Your app needs to store a list of orders. Servers keep adding orders to this list, and chefs take orders off the list and make them. It’s an order queue: servers add orders to the back of the queue, and the chef takes the first order off the queue and cooks it.

Would you use an array or a linked list to implement this queue? (Hint: Linked lists are good for inserts/deletes, and arrays are good for random access. Which one are you going to be doing here?)

Since I know that insertion and deletion operations run time complexity for Linked List is O for 1 that is constant time, and it is O for n in array. It is clearly mentioned in above scenario that insertion and deletions are operations are that performed regularly so I would with Linked List in this case.

Let’s run a thought experiment. Suppose Facebook keeps a list of usernames. When someone tries to log in to Facebook, a search is done for their username. If their name is in the list of usernames, they can log in. People log in to Facebook pretty often, so there are a lot of searches through this list of usernames. Suppose Facebook uses binary search to search the list. Binary search needs random access — you need to be able to get to the middle of the list of usernames instantly. Knowing this, would you implement the list as an array or a linked list?

In above scenario I would definitely choose array algorithm. It is because array allows random access instead of linked list that allows sequential access. In order to search usernames efficiently I must use the binary search algorithm as mentioned above that’s why it is essential to use array in order to use binary search algorithm.

Question: People sign up for Facebook pretty often, too. Suppose you decided to use an array to store the list of users. What are the downsides of an array for inserts? In particular, suppose you’re using binary search to search for logins. What happens when you add new users to an array?

When a user signs up for Facebook, newly going to be registered username is search in the database, if that is not found then new user is registered with a unique username.

Therefore, these are two operations that take place, first is search, and other is insertion. We know that run time complexity for reading in array is O for 1, and in linked list is O for n, and insertion run time complexity for array is O for n, and for linked list it is O for 1. It is important to understand that every time new user tries to signs up the Facebook, the search operation is performed at least once even if the user is already registered. New username is already registered or not is determined by searching from the database, then if the username is not found the insertion of new username takes place.

Using array in this scenario has some pros and cons briefly described ahead. Array provides random access that makes the application of binary search algorithm possible. Binary search is a powerful algorithm with run time complexity O of log n. Since the search takes place first, this point supports the use of array.

Secondly, when new username is added, the array will go through each element till the last to insert the newly added item there which defines the run time complexity of array for insertion as O for log n that is slower than linked list. Besides array requires continuous slots for its items that means if there is not memory space left for new item in the array right next to its last item, it won’t be inserted even if there is memory space somewhere else but not alongside the array. It will utilize another chunk of memory in that case. It is understandable here that you never know the number of new items to be added in the array. Trying to allocated dedicated memory slots for array may solve the problem for a while but this isn’t efficient use of computer memory.

Question: In reality, Facebook uses neither an array nor a linked list to store user information. Let’s consider a hybrid data structure: an array of linked lists. You have an array with 26 slots. Each slot points to a linked list. For example, the first slot in the array points to a linked list containing all the usernames starting with a. The second slot points to a linked list containing all the usernames starting with b, and so on.

Suppose Adit B signs up for Facebook, and you want to add them to the list. You go to slot 1 in the array, go to the linked list for slot 1, and add Adit B at the end. Now, suppose you want to search for Zakhir H. You go to slot 26, which points to a linked list of all the Z names. Then you search through that list to find Zakhir H.

Compare this hybrid data structure to arrays and linked lists. Is it slower or faster than each for searching and inserting? You don’t have to give Big O run times, just whether the new data structure would be faster or slower.

The hybrid model that is suggested above is definitely faster because it already reduces lot a greater number of operations that would be performed in using the array or linked list individually.

Every time the new user tries to register, that username is first searched from the database, if that username is not found then new username is inserted. Note that every attempt to sign up activates the search irrespective of whether insertion takes place or not.

If you user named Zakir H, tries to register then array will directly jump to its last index where linked list of names starting with Z are stored. Array allows random access therefore all operations of search that would take place when using linked list along have been reduced in this case.

After jumping to the required linked list search operation will be performed throughout the linked list because it only allows sequential search. Here the run time complexity will be O for n.

In case of insertion, first step of jumping to the required linked list will be same, and insertion run time for linked list in O for 1, that is constant time. It means the new username will be simply placed at last of linked list.

After considering above reasons, I think the hybrid model is way faster than individual approach.