[DSA] Linked List

Linked List (LL)

Let assume today is your first day in school and your are appointed as the class rep. Most likely the first task you and need to do is to write down the names and contact information of your class mates.

But how are you going to do it??? Do you randomly scribble the information on some paper napkins and shoved it into your bag? Or write down the names and contact information one by one, in a list form? Or fired up your web browser and point to docs.google.com and start making a spreadsheet? 

The data you have entered is unsorted, so this tiny piece of paper/document serves as your lookup table when you need to retrieve some information. E.g your classmate's phone number

This week, we are going to explore the several api calls to use STL list to insert data, manipulate data and to retrieve data.

Say you want to find out your new classmate catherine for her phone number. How would you look for the information in the list? Most of us would look from top to bottom, some bottom to up, some start in the middle and traverse up or down. Inherently, you still lookup the information from the list one by one. All this methods to find her name doesn't really matter, because the list of information is unsorted, it will still take n+1 effort . The effort to lookup a name in the list gets bigger when the list grow longer and longer.

In the list of names you have,how would you input new names for student that just got into your class? Do you add it at the end of the list? Or simply insert the name to any position where the space permits?

All the above is the analogy for the Linked List used in the computer

Items that is stored in Linked List have to be travsersed sequentially. There are no random access iterators to access link list. Hence, you need to declare an iterator of the same data type that is used by the STL list container.

When you are designing the code and you needed data to be access randomly, Linked list is not the best option. Traversing the whole list of items takes time. The time required will grow accordingly to the size of the list. So, vectors or arrays are the best option (at the moment of learning). The items in vectors and arrays are placed side by side in memory world and can be access in a random fashion.

Items of a Linked List are not required to be placed side by side in the memory of the computer. How items are "linked" in a link list are done by the maintaiannce of the "header" pointer and the "tail" pointer. Pointers, as we have learned in the previous sessions, are variables that store the memory address of the items we are interested with. The tail pointer of the current items contains the address of the next item, ie. the value stored in the head poiter.

0->hP|DATA1|tP->hP|DATA2|tP->hP|DATA3|tP->0


Changing the values of the pointer variable requires only O(1) effort. Hence, the linked list is efficient when data/items are required to be inserted randomly in the list.

If the deletion of an item is required in the linked list. All need to be done is to modify the tail pointer of the current item, skipping the item we want to delete and points to the head pointer of the item next to the deleted item. In other words, we are merely copying the address in the tail pointer of the deleted item to the previous item's tail pointer. cool huh. No more holes left in the memory, no more statically declared memory that is left unsed, no more ugly algorithm to compact the array after a deletion of items.

All the above, are naked to the untrained eye. Users can't see the differences, only the programmer does.

DRill Questions:
1. create a list to store name of your classmates.
2. print out class list
3. "find" a particular person in the list. return found or not found.
4. Find out a method to attach the gpa score to the names in the list above.
hint: use class and OOP.
5. sort the list by gpa descending.
hint, try out stl algorithm