In singly linked list nodes have one pointer (Next) pointing to the next node, whereas nodes of doubly linked lists have two pointers (prev and next). Prev points to the previous node and next points to the next node in the list.

Advantages

Linked lists have many advantages. Some of the very important advantages are;

1.      Linked lists are dynamic data structures. That is they can grow or shrink during the execution of a program.

2.      Efficient memory utilization. Here memory is not pre-allocated. Whenever it is required. And it is deallocated (removed) when it is no longer needed.

3.      Insertion and deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of a data item from the give position.

4.      Many complex applications can be easily carried out with inked lists.

Disadvantages

1.      More memory: if the number of fields is more, then more memory space is needed.

2.      Access to an arbitrary data item is little bit cumbersome and also time consuming.

KEY TREMS

AS you know a linked list is a non-sequential collection of data items called nodes. There nodes in principle are structures containing fields. Each node in a linked list basically two fields.

1.      Data field

2.      Link field

The data field contains an actual value to be stored and processed and the link field contains the address of the next data item in the linked list. The address used to access to particular node is known as pointer. Therefore the elements in a linked list are ordered not by their physical placement in memory but their logical links stored as part of the data within the node itself. In other words, the logical and physical ordering of data items in a linked list need not be the same. But in sequential representation these ordering are the same.

NULL Pointer

Note that the link field of the last node contains NULL rather than a valid address. It is a null pointer and indicates the end of the list.

External pointer

It is a pointer to the very first node in the linked list it enables us to access the entire linked list.

Empty list

It the nodes are not present in a linked list, then it is called an empty linked list or simply empty list it is also called the null list.

The value of the external pointer will be zero for an empty list. A linked list can be made an empty list by assigning a NULL value to the external pointer. That is in our case.

                                Start= NULL

Notations

Let p be s pointer to node in a linked list. Then we can form the following notations. To do something on linked lists.

·         Node (p); node pointed to by the pointer p,

·         Data (p); data of the node pointed to by p,

·         Link (p); address of the next node that follows the node pointed to by the pointer p.

Suppose if the value p= 2000, then

                        Node (p) = node (2000) =

Is the second node, and

                        Data (p) = data (2000)=20

                        Link (p) = link (2000) = 3000

Which is the address of the third node?