Linked List and It’s Application
Linked List is a sequence of links that contain items. Each link contains a link to another link.Each link carries data fields and a link field called next. The Link List contains a linked item called the first. Each link is linked to its next link using its next link. The last link considers the link useless to mark the end of the list.
You might be wondering why we need a linked list when we have an array?
Here are some array barriers:-
Size of an each array is fixed. So we have to know the maximum limit on the number of items in advance. And, generally, shared memory is equal to the upper limit regardless of usage.Adding something new to the array is expensive because the room has to be renovated and the existing room items have to be shifted.
Linked list representation
The linked list is represented by the pointer that goes to the first node of the linked list. The first node is known as head. If the linked list is empty, then the head value is NULL. Each node in the list contains at least two components
data ,Pointer to the next node
The basic operations supported by a list are,
- Installation — Adds an item at the beginning of the list
- Deletion — Deletes an item at the beginning of the list
- Show — Displays complete list
- Search — Search an item using a given key
- Delete — Delete an item using a key
Link List Types
- Simple Linked List — Item navigation is advanced only.
2. Doubly Linked List — Items can be navigated from back and forth.
3. Circular Linked List — The last item contains a link to the first item as next and the first item has a link to the last item as before.
Let’s take an example
We all use browsers like Chrome, Firefox, Safari etc daily. All these browsers have this great feature of archiving history. They have provided two easy posts to go back and forth in our search history. What do you think is the easiest way to achieve this?
Yes you are right. Linked List
To achieve this the browsers uses a doubly linked list. The doubly list is inevitably linked making it easy to move back and forth easily.
As I said above in the popular doubly list node has 3 parts namely previous, data and next. The previous one contains references to the previous node and the next contains the reference to the next node. With this type of structure we can track the flow of everything easily and that is why we can use it to go back and transfer the browsers feature today.
When we did the first search the first node was created .
- Head is updated with the newly created node record
- A recent redesigned node previous updated is with a head reference.
- Newly created nodes next is still set to NULL cause we haven’t traveled future from that page.
So whenever we click a certain link on the current page and go to the new page…
- A new node has been created
- The following previous nodes update with reference to newly created nodes.
- Newly created nodes are updated according to the previous node.
- The newly created node is set to NULL.
The above 4 steps are repeated as we continue to visit more pages. And this is how our browsing history is maintained.
Thanks for reading…!