link List

A linked list is a sequence of data structures, which are connected together via links.

Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.

Types of Linked List

• Simple Linked List −> Item navigation is forward only.

• Doubly Linked List −> Items can be navigated forward and backward.

• Circular Linked List −> Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations

Following are the basic operations supported by a list.

• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.

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

• 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.

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