Linked List Data Structure

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Applications of linked list in computer science –

1.   Implementation of stacks and queues

2.   Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices.

3.   Dynamic memory allocations 1: We use linked list of free blocks.

4.   Maintaining directory of names

5.   Performing arithmetic operations on long integers

6.   Manipulation of polynomials by storing constants in the node of linked list

7.   representing sparse matrices

Applications of linked list in real world-

1.   Image viewer – Previous and next images are linked, hence can be accessed by next and previous button.

2.   Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list.

3.   Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.

Applications of Circular Linked Lists:

1.   Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.

2.   Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

3.   Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

Why do I need a linked list and why is it important?

The usefulness of a linked list is it's constant time insertion and deletion for any arbitrary node. Off the top of my head, queues benefit greatly from this feature, since they aren't searching for an item, and only inserting/deleting at the ends of the list.

You can get away with an array, but arrays only have constant time for adding and removing the last object. Compound that with the memory and operation overhead from deleting the first element and arrays start looking pretty sour . Arrays can impose an additional cost on adding an item if the array  needs to be resized. Deletion of the last element is the only guaranteed  constant time operation. Additionally, linked lists make some favorable tradeoffs in memory. For the added memory cost of the pointer per node, adding and deleting elements doesn't need additional memory that array resizing would require, making memory allocation more predicable for a given input.

That is, unless the library handling your dynamic array memory doesn't resize to a smaller array to minimize space.

When would you use a linked list?

 

With an array, you would need to move lots of elements ‘to the right’ to make room for a new element in the middle or ‘to the left’ to fill the hole if you remove an element in the middle. That is: if you insist that the original order is maintained. Else you could add new elements to the end of a vector. Removing a value in the middle (if order doesn’t matter) can be done by overwriting it with the last element and then making the vector one smaller. That would still have complexity O(1), constant time. Note: you may have to delete the element that is removed or free it. The latter is uncommon, cause then you would mix C style malloc with C++ STL.

Linked lists are often sorted in some way and you want to maintain the proper order at all times. Although they allow for fast removal and insertion, they have poor cache performance due to poor space locality: all nodes can be ‘anywhere’ in memory, they are not at neat consecutive locations. Also, the pointers to the next node (and previous node in case of double linked list) take extra memory. Thus for small lists it is better to use a vector or an array. Perhaps you can first build the vector or array and sort when you are done adding all items.