Linked List

We have said earlier that most of the times, meanings of words are contained in the words themselves; all you have to do is ponder over them. The term Linked List emphasises on two parts -

  1. It is a List. This means it is a linear structure where one element comes after another and for any element in the list, there are at most 2 adjacent elements. (Note: These elements are sometimes referred to as nodes too.)
  2. It is a Linked list. If you remember the data structures discussed till now, you might notice that all of them are linear where each element has at most two adjacent elements and thus are logically a ‘list’ anyway. The part which separates the previously mentioned data strucures is where we mention the keyword “Linked”. The reason Linked Lists are called as such is because the elements of a Linked List may not necessarily be placed adjacent to each other in the memory. Instead, they can be placed arbitrarily in the memory. Each element of the list however contains the link to the next element in the list (hence the term linked).

Linked Lists like arrays can also be used as a base data structure for other list-based data structures. For example, you can implement Stacks and Queues (all types of queues) using Linked List as well as arrays. Fact is, they are more flexible to use than arrays because:

  1. In most cases the size of array has to be pre-determined. So if you created an array of 50 elements and implemented a stack using this array, you cannot push 51 elements into this stack. However, with Linked List, it is possible to add yet another element as long as there is memory available on the system.
  2. If you want to add an element somewhere in the middle of an array, you would have to rearrange the rest of the array. For example: Assume you created an array of size 50 and filled in 40 elements. If you want to add a new element at position 10 of the array, then you would have to rearrange elements 10 through 40 by shifting one place to their right so that position 10 becomes empty. Only then can you add an element at position 10. Such is not the case with Linked Lists. You can create an element and adjust the next-element pointers of two elements and you would have inserted a new element in the list.
  3. There is one disadvantage of Linked List against array though - when it comes to array, we can fetch any (n th element in one go. With Linked Lists, if we want to access the n th element, then we have to access all the n-1 elements before that element.

How does the Linked List work?

Linked Lists are mostly implemented using a structure which has two elements - 1) a data element which contains the value of that node. 2) a link-pointer which can point to a similar structure as one in which this pointer is contained. When you want to add a new element at the end of the list, you can create a new element with link-pointer pointing to null and make the link-pointer of the current last element point to the new object which was created. This way, one can create a very large list as long as there is space in the system memory (RAM).

It is worth noting that the pointer to first element is stored separately. It is also worth nothing (though we have already mentioned it) that to access any element, you have to start at the beginning of the list and follow the links of the subsequent elements until you reach the desired element. This is called traversal of the list.

The operations on a Linked List are:

  1. Add an element at the end of list: For doing so, you first create the new element with desired data value. Then traverse the list and reach the last element and set its link-pointer to the location of the newly created element.
  2. Add an element at the beginning of the list: In this case, you create a new element and set its link-pointer to the first element’s address. Then, you update the pointer to first element with the address of the newly created element.
  3. Add an element at a particular position in the list: You will have to follow these steps -
    1. Create the new element with desired data value. Keep the link-pointer as null. Let’s call this element as N (standing for ‘new’).
    2. Traverse the list until you reach the desired element. Let’s call this element as D (standing for ‘desired’). Now, D must be pointing to another element. Let’s call that element E (it is next to D).
    3. Copy the address of E from D’s link-pointer and set it as the link-pointer value of N.
    4. Set the address of N as the link-pointer value of D.
    5. Now, D is pointing to N and N is pointing to E; just as we wanted. You have inserted a new element in the Linked List.
  4. Remove an element from end of list: Traverse the list till you reach the second-last element. Get the last element and destroy it (deallocate memory held by it). Set the link-pointer of the second last element to null, thus making it the last element of the list.
  5. Remove an element from beginning of the list: Get the first element (let’s call it F) and copy the link-pointer value. Now destroy F (again, deallocate the memory held by it). Set the pointer of the first element to the copied link-pointer value.
  6. Remove an element at a particular position in the list: You would follow these steps to remove an element at a particular position:
    1. Traverse the list and reach the element which points to the desired element. Let’s call this element C (comes before ‘desired’).
    2. Get the element pointed to by C. Let’s call it D (standing for ‘desired’).
    3. Get the link-pointer value of D. Copy this value to the link-pointer of C. Now C is pointing to E.
    4. Now destroy D (deallocate the memory taken up by D).
    5. Now C points to E and the desired element (D) has been removed from the list.

You can see that we have covered all the operations required for operations of a stack and queue. If you remember circular queues, you might realise why it is easier to implement them using a Linked List - all you have to do is maintain the front and rear pointers and perform the operations of removing elements from the front of the list and adding them at the end.

Rules of the Linked List

We have described the operations related to the Linked List in detail already and the rules should be clear. The following rules related to linked list should be kept in mind:

  1. The pointer to the first element is stored separately.
  2. No element points to any element before it. Doing so would create a circular list, which is not something we desire.
  3. The link-pointer of the last element must point to nothing (null).
  4. To get to any element (to search for the element), you would want to start from the beginning and traverse the list until you reach that element.

Usage

Linked lists are used at many places and can act as an alternate base-implementation of other structures like lists, arrays, stack and queues. One might wonder - if Linked Lists can be used as a base for other list type data structures, why on earth are they not used everywhere; why have two data structures - arrays and linked lists? The answer to that is - “Because they both have their pros and cons”

When should one use Arrays instead of Linked Lists

  1. When you need to access your elements randomly - Arrays are indexed and you can access every element using its index. For example, if you have an array of 10 integers (named arr and you want to access the 9th element, you can just write arr[8] to access the element (remember, array indexing starts from 0, not 1). Whereas if you had a linked list of 10 integers, you would have to traverse the list by visiting each element until you reach the 9th element.
  2. When you need to work on each element of the item one by one at a very fast rate - In some lower level languages (like C), you can use the pointer mathematics with the array. Since all elements in such languages are bound to be of the same size, you can just add memory offsets for each element starting from the first element. This is not possible for linked lists.
  3. When you know the number of elements you need to store - Memory allocation for Linked Lists are dynamic whereas for Arrays, the memory is allocated only once. For lower level languages like C, the allocation is always contiguous. Since arrays can be accessed at a rapid speed, usage of arrays saves time in such cases.
  4. When every single byte of memory matters - this might not be the case with Servers and Desktop machines where Gigabytes of RAM is a norm, some embedded devices are short on memory. Creating Linked List would take more memory for such cases because each element of a Linked List has to contain the data and the pointer to the next element. Normally, the pointer to the next element has to be one word wide. Remember that Integers are also (normally) one word wide, which is 64 bits for a 64-bit processor. So if you were to create an array of 100 integers, you would take up 6400 bytes whereas if you create a Linked List of 64 integers on the same machine, it would take up 12800 bytes - which is double the size of the array.

When should one use Linked Lists instead of Arrays

  1. When there is no need to access elements randomly - In some data structures such as queues, you would hardly, if every want to access an element which is in not at the beginning or the end of the structure. Linked List is perfect for such use cases.
  2. When you need to insert items at constant time - An array is put in a pre-defined space; the memory address range is reserved for that array. For larger arrays, that is a problem because if all of the space is not used, then we are wasting memory space. To adjust for that, programmers (and higher-level languages like PHP and Ruby) create smaller arrays to begin with and as more elements are inserted, the array size is increased and reallocated. This increases the time taken to insert a single element as the array grows. Element insertion in Linked Lists always takes the same amount of time (at least till there is memory available in the RAM and the Operating System does not have to suspend pages to disk). This makes the insertion time predictable which is important for some real-time applications.
  3. The number of items is unknown - Memory addresses for an array have to allocated at the time array is declared and the number of items have to be known beforehand for the lower level languages. This is not always the case though. Sometimes, the programmer cannot predict the number of items that might come in. In such a case, it is better to use Linked Lists instead of arrays.
  4. When you might need to insert items in the middle of the list - If you are creating a list which is sorted, or are creating a priority queue (which depends on the sorted attribute of a list), using a Linked List would make more sense because inserting an item in between is much easier with a Linked List; whereas with Arrays, you would have to manually shift elements to make space for the new item you want to insert somewhere in the middle of the list.

Updated: