Linked Lists:

A linked list is a linear collection of data elements called nodes. The linear order is given by means of pointers. Each node is divided into two parts: the data part and the link part.

The data part contains the data that is to be stored and the link part contains the address of the next node in the list.



A linked list with four nodes.

The linked list also contains a list pointer variable called the Start pointer that contains the address of the first node in the list. We need this pointer in order to get the address of the linked list and to go through the list whenever required.

The end of the list is marked by a special pointer known as the NULL pointer.

The Start and the Null pointer are very necessary in order to perform operations on the linked lists. 

Representation of linked lists in memory:

Start      = 20 , Info[20] = W (The first character of the list)

Link[20]= 29 , Info[29]= E

Link[29]= 31 , Info[31]= L

Link [31]= 35, Info[35]= C

Link[35]= 39 , Info[39]= O

Link[39]= 45, Info[45]= M

Link[45]= 50 , Info[50]= E (The last character of the list)




Memory representation of linked lists



Need for use of linked lists:

1. The successive elements of linked lists do not need to occupy the adjacent memory space in the memory unlike arrays as is shown in the figure above.

2. Dynamic allocation of memory leaves us with an ease of  including more data into the list.

3. . Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.

Disadvantages of Linked lists:

1. Linked lists do not allow random access to the data other than the first node's data, or any form of efficient indexing. Many basic operations like obtaining the last node of the list or finding a node that contains a given datum, or locating the place where a new node should be inserted may require scanning most or all of the list elements.