singly liked list and insertion in singly linked list

1)   Singly linked list –

·       Singly linked lists contain nodes which have a data part as well as an address part.

·       The data part is used to store the data.

·       And the address part is used to store the address of next node in a sequence

·       A singly linked list is the simplest type of linked list.

·       In singly linked list the pointer start always point first node.

·       In singly linked list there is NULL in the next part of last node.

·       The operation we can perform on singly linked list –

a)     Traversing

b)     Insertion

c)     Deletion

·       Before we implement actual operations, fist we need to setup empty list. First perform the following steps before implementing actual operations.

Step 1: Include all the header files which are used in the program.

Step 2: Declare all the user defined functions.

Step 3: Define a Node structure with two member’s data and next

Step 4: Define a Node pointer 'head' and set it to NULL.

Step 4: Implement the main method by displaying operations menu and make suitable function calls in the main method to perform user selected operation.

Traversing – traversing a linked list means accessing the nodes of the list in order to perform some processing on them.

Example –

                       

Algorithm of traversing a singly linked list – We can use the following steps to display the elements of a circular linked list...

·Step 1: Check whether list is Empty (head== NULL)

·Step 2: If it is Empty, then display 'List is Empty!!!' and terminate the function.

·Step 3: If it is Not Empty then, define a Node pointer 'ptr' and initialize with head.

·Step 4: Keep displaying ptr → data with an arrow (--->) until ptr reaches to the last node

·Step 5: Finally display ptr → data with arrow pointing to head →data.

a)     Insertion in singly linked list – insertion means to adds or insert a new element in a singly linked list. there are three  cases of insertion –

                                i.            Insert a new node at the beginning

                             ii.            Insert a new node at the middle

                           iii.            Insert a new node at the end

       I.            Insert a new node at the beginning – in this we insert the new element at the beginning of the list.

Algorithm of insert node beginning –

·         Step 1: Create a new_node with given value.

·         Step 2: Check whether list is Empty (head== NULL)

·         Step 3: If it is Empty then, set new_node→next = NULL and head = new_node.

·         Step 4: If it is Not Empty then, set new_node→next = head and head = new_node.

     II.            Insert a new node at the middle (after) - We can use the following steps to insert a new node after a node in the single linked list...

Algorithm of insert node after a given node

·Step 1: Create a new_node with given value.

·Step 2: Check whether list is Empty (head== NULL).

·Step3: If it is Empty then, set new_node → next = NULL and head = new_node

·Step 4: If it is Not Empty then, define a node pointer preptr and initialize with head.

·Step 5: Keep moving the preptr to its next node until it reaches to the node after which we want to insert the new_node (until preptr→ data is equal to location, here location is the node value after which we want to insert the new_node).

·Step 6: Every time check whether preptr is reached to last node or not. If it is reached to last node then display 'Given node is not found in the list!!! Insertion not possible!!!'and terminate the function. Otherwise move the preptr to next node.

·Step 7: Finally, Set ' new_node → next = ptr → next' and 'preptr → next = new_node.

   III.            Insert a new node at the middle (before) - We can use the following steps to insert a new node before a node in the single linked list...

Algorithm of insert node before a given node

·Step 1: Create a new_node with given value.

·Step 2: Check whether list is Empty (head== NULL)

·Step3: If it is EMPTY then, set new_node → next = NULL and head = new_node.

·Step 4: If it is Not Empty then, define a node pointer ptr and initialize with head.

·Step 5: Keep moving the ptr to its next node until it reaches to the node after which we want to insert the new_node (until ptr → data is equal to location, here location is the node value after which we want to insert the new_node).

·Step 6: Every time check whether ptr is reached to last node or not. If it is reached to last node then display 'Given node is not found in the list!!! Insertion not possible!!!'and terminate the function. Otherwise move the ptr to next node.

·Step 7: Finally, Set ' new_node → next = ptr → next' and 'preptr → next = new_node.

  IV.            Insert a new node at the end - We can use the following steps to insert a new node at end of the single linked list...

Algorithm of insert a node at the end

·Step 1: Create a new_node with given value and new_node → next as NULL.

·Step 2: Check whether list is Empty (head== NULL).

·Step 3: If it is Empty then, set head = new_node.

·Step 4: If it is Not Empty then, define a node pointer ptr and initialize with head.

·Step 5: Keep moving the ptr to its next node until it reaches to the last node in the list (until ptr → next is equal to NULL).

·Step 6: Set ptr → next = new_node.

b)     Deletion – deletion means removing element from the list. There are three cases of deletion –