Link list (Insert operation)

Link list -: 

                 A linked list is a collection of nodes and every node in the list contains two fields as

                     - Data or information field

                     - Next address or pointer field

The information field holds the actual data item and next address fields contains the address of the next node in the list. The address of any node is maintained by pointer. The next address field of last node in the list contains a special value known as NULL, which is not a valid address. The NULL pointer is used to signal the end of list.

Insert fig here

The list with no nodes is called empty or NULL list. The first node of the list is called front or head and the last node of the list is called rear or tail. The next node to the head of the list is called successor and a node previous to any node is called predecessor.

Types of linked list

1.      Linear singly linked list

2.      Circular linked list

3.      Two-way or doubly linked list

4.      Doubly circular linked list

Singly linked list

The simplest kind of linked list is singly linked list, which has one link per node. This link points to

the next node in the list or to a null value or empty list if it is the final node.

Fig: a singly linked list with three nodes.

Basic operation in singly linked list

Some of the basic operations that may be performed on a linked list are:

-          Create a list

-          Check for empty list

-          Insert a node on the specified location in the list (we can insert a new node either at front or rear or after a particular node).

-          Delete an element from a list (we can delete first node, last node, a particular node and a node after the given node).

-          Update an element of the list.

-          Search an element of the list

-          Sort the list.

-          Print the entire list.

Advantages of link list

1.      Linked list is a dynamic data structure; the size of list can grow or shrink during program execution. So, maximum size need not be known in advance.

2.      The linked list does not waste memory

3.      It is not necessary to specify the size of list, as in array.

4.      It provides flexibility in allowing the items to be rearranged.

Insert operation

1. Insert at first

1.      Allocate space in memory for new node and place the information in the information field of newly created node.

2.      Check the linked list, if it is empty make this new node as the first and last node of linked list.

3.      If link list is not empty then place the address of first node in the next address field of newly created node.

4.      Make new node as the first node of the linked list.

Algorithm InsertBegin(head,elt)

[Adding element elt at the beginning of the list pointed by head]

1.      new <- getnode(NODE)

2.      data(new) <- elt

3.      next(new) <- head

4.      head <- new

 

Fig: insert at beginning

  

      2. Insert at last

1.      Allocate space in memory for new node and place the information in the information field of newly created node and make the next field of new node as null.

2.      Check the linked list, if it is empty make this new node as the first and last node of linked list.

3.      If linked list is not empty then get the address of the last node traversing from beginning pointer and place the address of newly created node in the next address field of last node.

4.      Make new node as the last node of the linked list

Algorithm InsertEnd(head,elt)

[Adding the element elt at the end of the list]

1.      new <- getnode(NODE)

2.      data(new) <-  elt

3.      next(new) <- null

4.      if(head = = null)

head <- new

else

temp <- head

5.      while(next(temp)!=null)

temp <- next(temp)

6.      next(temp) <- new

Fig: Insert at last in link list

     3.Insert after a particular node

1.      Search the node in the list.

2.      If node is not in the list then display an error message “insertion is not possible”

3.      Allocate space in memory for new node and place the information in the information field of newly created node.

4.      If node is the last node of the list then:

a.       Place the address of newly created node in the next address field of last node.

b.      Make new node as the last node of the linked list

5.      Otherwise

a.       Assign next address of given node in a variable temp1

b.      Assign address of new node in the next address field of given node.

c.       Assign temp1 to next address field of new node.

Algorithm insertafter( NODE P, x)

 [insert a node containing value x after node P]

  1. Search the node by traversing the list.

  2. if(P=null)

         printf("cannot be inserted");

  3. else

           Q=getnode();

           Q(info)<- x;

           Q(next)<-P(next);

           P(next)<-Q;