Data Structure - Linked List

Dynamic memory management is best understood using the concepts of data structure. Data structures use dynamic memory management to allocate and deallocate memory during the run time.

Linked List  : Linked list can be defined as a logical chain of memory blocks (called nodes)where each block contains data as well as the address of the next logical node in the collection. To understand it better, let's compare a linked list with an array. An array is a collection of values of similar types. When we declare an array, we are only concerned about the data that we want to store in the array, not the memory. Memory to an array is assigned automatically by the compiler in contiguous form. Contrary to this the "elements" of a linked list not only store the data as arrays do, they also store the address of the next node in the chain.

Why do nodes store the address?
You may be wondering about what is the need to store the address of any node. This is what data structures are all about. Since memory to a data structure, like linked list is allocated dynamically during the runtime, it is not known beforehand what will be the address of the next created node. It is just the opposite of array where each element is addressed relative to the previous element. When the address of a node is not known, how will we access its data? That's why we keep track of the address of the nodes as well.

Basic operations on a linked List

A link list allows the following operations on it.

1. Insertion : A new node can be added to a list at the beginning, middle or at the end.
2. Traversal : Traversal is the process in which we can read the nodes of the linked list one by one.A double link list can be traversed both ways, from beginning to end and to end to beginning.
3. Deletion : Being a data structure, linked list allows the user to delete unused nodes from the collection.
4. Searching : A linked list can be searched for a particular information as well. This is done by reading the list from "start" till the end.

Types of linked list
1. Single Linked List
2. Double Linked List
3. Circular Linked List

Single Linked List : A single linked list is a linked list where each node stores the address of the next node. A special pointer which is usually called "start" or "head" points to the first node of the collection.
This is how a single linked list looks like.

Single Linked List

As you can see each node is divided into two parts, data and address. Data contains any type of data that we want to store like "no,name, teleno" etc. The address part contains the address of the next node. The last node of a single linked list contains "NULL", since there is no node to which it can point. To access a linked list, all we have to do is to find the node to which "head" is pointing to, from thereon all nodes are connected so we can easily move from one node to another. The compiler assumes that there is always a possibility that new nodes will be inserted in the list, therefore there should be some methodology to allocate unused memory for the new nodes. Also, there must be some technique to release memory of the deleted nodes. This technique is incorporated by C, using a special list which contains the information about unused memory cells. This list has its own pointers pointing to the next free node and is called "Free-Pool". When a new node is added the number of free nodes is reduced and with every deletion the number increases.

Application of Linked List

1. The main Applications of Linked Lists are
2. For representing Polynomials
3. It means in addition/subtraction /multiplication of two polynomials.
4. Eg:p1=2x^2+3x+7 and p2=3x^3+5x+2
5. p1+p2=3x^3+2x^2+8x+9
6. In Dynamic Memory Management
7. In allocation and releasing memory at runtime.
8. In Symbol Tables
9. In Balancing parentheses
10. Representing Sparse Matrix