This blog is under construction

Sunday, 24 February 2013

C Program To Implement Singly Linked List - Insertion, Searching, Traversal, Delete Node and Delete List

Singly Linked list is a data structure in which each node contains a data field and next(pointer) field.  And the next pointer contains reference to the next node  in the list.

      ptr1(1200)          ptr2(1400)            ptr3(NULL)
+-------------+       +-------------+       +---------------+
| 25  |ptr1 -|---->| 30  | ptr2 -|---->| 40  | ptr3  -|--->X
+-------------+       +-------------+       +---------------+
n1(1000)                n2(1200)                n3(1400)

 n1(node1), n2(node2) n3(node3) - nodes
ptr1(1200) - pointer to node2 with address 1200
ptr2(144) - pointer to node3 with address 1400
ptr3 - pointer of the last node always points to NULL.

 Structure of a node:
struct node {
int data;
struct node *next;
};

                              +---------------------------------+
                             |      data       |      next       |
                             +---------------------------------+
                                                node

 How to create a node in linked list?
Dynamically allocate memory for the new node, fill the given data in it and return the new node to the caller.

 struct node createNode(int data) {
   struct *newnode  =  (struct node *)malloc(sizeof (struct node))
   newnode->data = data;
   newnode->next = NULL;
   return (newnode);
}
How to insert a node into a linked list?
  next(1200)           next(1400)            next(NULL)
+-------------+       +--------------+       +--------------+
| 25  |next -|---->| 30  | next -|---->| 40  | next -|--->X
+-------------+       +--------------+       +--------------+
  n1(1000)                n2(1200)                n3(1400)

 Insert a new node(n4) after node n2.

 Traverse the list from the head node(n1) to the node(n2) after which the new node needs to be inserted.
n4 = createNode(50);
n4->next = n2->next;
n2->next = newnode;
Note: n4 is the new node here

 next(1200)           next(1500)       next(1400)         next(NULL)
+-------------+     +--------------+    +-------------+     +---------------+
| 25  |next -|-->| 30  | next -|-->| 50 | next -|-->| 40  | next  -|--->X
+-------------+     +--------------+    +-------------+     +---------------+
n1(1000)                n2(1200)          n4(1500)         n3(1400)   
How to delete a node from a linked list?
 next(1200)           next(1500)       next(1400)         next(NULL)
+-------------+     +--------------+    +-------------+     +--------------+
| 25  |next -|-->| 30  | next -|-->| 50 | next -|-->| 40  | next -|--->X
+-------------+     +--------------+    +-------------+     +--------------+
n1(1000)                n2(1200)          n4(1500)         n3(1400)   

 Traverse the list from the head node(n1) to the node(n2) that is present previous to the node(n4) which needs to be deleted.

   temp = n2->next; // temp points to node n4
  n2->next = temp->next;  // n2->next points to node n3
  free(temp); // delete node n4

 next(1200)           next(1400)            next(NULL)
+-------------+       +--------------+       +--------------+
| 25  |next -|---->| 30  | next -|---->| 40  | next -|--->X
+-------------+       +--------------+       +--------------+
n1(1000)                n2(1200)                n3(1400)
How to search a node in a linked list?
Traverse the list from the head node(n1) until we find a node with the given value.  If we have traversed the entire list and could not find a node with the given value, then the given data is not present in the list.

 struct node * searchNode(int data) {
    struct node *temp = n1; //n1 is the head node
    while (temp) {
        if (temp->data == data) {
    printf("Data Present\n");
            return temp;
        }
       temp = temp->next;
    }
    return NULL;
 }

See Also:


C Program To Implement Singly Linked List:


  #include<stdio.h>
  #include<stdlib.h>

   struct node* createNode(int);
  struct node* findNode(int);
  void insertAtStart(int);
  void insertAtEnd(int);
  void insertAtPos(int, int);
  void findNext(int);
  void findPrevious(int);
  void deleteList();
  void deleteElement(int);
  void isListExist();
  struct node {
        int data;
        struct node *next;
  };

   struct node *head = NULL;
  struct node *tail = NULL;

   /*
   * creates node and fill the given data
   */
  struct node * createNode(int data) {
        struct node *ptr = (struct node *) malloc(sizeof (struct node));
        ptr->data = data;
        ptr->next = NULL;
        return ptr;
  }

  void insertAtStart(int data) {
        struct node *ptr = createNode(data);
        /*
         * if head is NULL, list not yet created. So,
         * head and tail will be newly created node
         */
        if (head == NULL) {
                head = ptr;
                tail = ptr;
                return;
        }
        /*
         * Adding node at the beginning of the list
         * and the newly created node is the head hereafter
         */
        ptr->next = head;
        head = ptr;
  }

  void insertAtEnd(int data) {
        struct node *ptr =  createNode(data);

        /*
         * if tail is NULL, list not yet created. So.
         * head and tail will be newly created node.
         */
        if (tail == NULL) {
                head = ptr;
                tail = ptr;
        }

        /*
         * Adding node at the end of the list and the
         * newly created node is the tail here after
         */
        tail->next = ptr;
        tail = ptr;
  }

  void insertAtPos(int pos, int data) {
        struct node *temp, *ptr = createNode(data);
        int i = 1, inserted = 0;

        /*
         * if head is NULL and position is 1, it means
         * user requests to create a first node of the
         * list
         */

        if (head == NULL || pos == 1) {
                if (!head) {
                        head = ptr;
                        tail = ptr;
                        return;
                }
                ptr->next = head;
                head = ptr;
                return;
        }
        temp = head;
        while (temp) {
                /* inserting node at the give postion */
                if (pos == i + 1) {
                        ptr->next = temp->next;
                        temp->next = ptr;
                /*
                 * if the node is inserted at the end
                 * then the newly attached node is tail
                 */
                        if (ptr->next == NULL)
                                tail = ptr;
                        inserted = 1;
                        break;
                }
                i++;
                temp = temp->next;
        }
        if (!inserted)
                printf("u ve entered wrong position\n");
  }

  struct node* findNode(int data) {
        struct node *ptr;
        int found = 0;
        ptr = head;
        while (ptr) {
                /*
                 * searching for 1st occurance of data in
                 * linked list
                 */
                if (ptr->data == data) {
                        found = 1;
                        break;
                }
                ptr = ptr->next;
        }
        if (found)
                return (ptr);
        else
                return (NULL);
  }

  void findPrevious(int data) {
        struct node *ptr;
        int found = 0;
        ptr = head;
        while (ptr != NULL && ptr->next != NULL) {
                if (ptr->next->data == data) {
                        found = 1;
                        break;
                }
                ptr = ptr->next;
        }
        if (found)
                printf("Value present previous to %d is %d\n",
                        data, ptr->data);
        else
                printf("No prev data available for ur input\n");
  }

  void findNext(int data) {
        struct node *ptr;
        int found = 0;
        ptr = head;
        while (ptr && ptr->next != NULL) {
                if (ptr->data == data) {
                        found = 1;
                        break;
                }
                ptr = ptr->next;
        }
        if (found)
                printf("Value present next to %d is %d\n",
                        data, ptr->next->data);
        else
                printf("No next data available for ur input\n");
  }

  void deleteNode(int data) {
        struct node *ptr, *temp;
        int res = 0;
        ptr = head;
        if (ptr->data == data) {
                if (ptr->next == NULL) {
                        free(ptr);
                        head = tail = NULL;
                }
                head =  ptr->next;
                free(ptr);
                return;
        }

        while (ptr != NULL && ptr->next != NULL) {
                if (ptr->next->data == data) {
                        temp = ptr->next;
                        ptr->next = temp->next;
                /*
                 * if last node is deleted, update tail value
                 */
                        if (ptr->next == NULL)
                                tail = ptr;
                        free (temp);
                        res = 1;
                }
                ptr = ptr->next;
        }
        if (!res)
                printf("Operation failed - Give data unavailable in list\n");

  }

  void deleteList() {
        struct node *ptr;
        ptr = head;
        while (ptr){
                head = ptr->next;
                free(ptr);
                ptr = head;
        }
  }

  void walkList() {
        struct node *ptr;
        int i = 1;
        ptr = head;
        while (ptr) {
                printf("+--------------------------+\n");
                printf("|Node[%d] addr:%10u   |\n", i, (unsigned int) ptr);
                printf("+--------------------------+\n");
                printf("|data = %3d                |\n", ptr->data);
                printf("+--------------------------+\n");
                printf("|next = %10u         |\n", (unsigned int)ptr->next);
                printf("+--------------------------+\n");
                ptr = ptr->next;
                if (ptr) {
                        printf("       || \n");
                        printf("       || \n");
                        printf("       \\/ \n");
                }
                i++;
        }
  }

  void isListExist() {
        if (head)
                printf("List is available\n");
        else
                printf("List is unavailable\n");
  }

  int main () {
        int flag = 1, ch, data, pos, result;
        while (flag) {
                printf("########################################\n");
                printf("1. Insertion at the start of List\n");
                printf("2. Insert at the end of list\n");
                printf("3. Insert at node at the given position\n");
                printf("4. Find node\n");
                printf("5. Find Previous data value\n");
                printf("6. Find next data value\n");
                printf("7. Delete node\n");
                printf("8. Delete list\n");
                printf("9. Walk list\n");
                printf("10. Is list exists\n");
                printf("11. Exit\n");
                printf("########################################\n");
                printf("Enter ur choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter data to insert into list\n");
                                scanf("%d", &data);
                                insertAtStart(data);
                                break;
                        case 2:
                                printf("Enter data to insert into list\n");
                                scanf("%d", &data);
                                insertAtEnd(data);
                                break;
                        case 3:
                                printf("Enter value for position and data\n");
                                scanf("%d%d", &pos, &data);
                                insertAtPos(pos, data);
                                break;

                        case 4:
                                printf("Enter value for data to be searched\n");
                                scanf("%d", &data);
                                struct node *ptr = findNode(data);
                                if (ptr)
                                   printf("Give node is present in the list-"
                                        "data:%d\n", ptr->data);
                                else
                                   printf("Give data is not available in list\n");
                                break;
                        case 5:
                                printf("Enter value to get previous value\n");
                                scanf("%d", &data);
                                findPrevious(data);
                                break;
                        case 6:
                                printf("Enter value to get next value\n");
                                scanf("%d", &data);
                                findNext(data);
                                break;
                        case 7:
                                printf("Enter value to delete node\n");
                                scanf("%d", &data);
                                deleteNode(data);
                                break;
                        case 8:
                                deleteList();
                                break;
                        case 9:
                                walkList();
                                break;
                        case 10:
                                isListExist();
                                break;
                        case 11:
                                flag = 0;
                                break;
                        default:
                                printf("Pleae retry once again\n");
                                break;
                }
                printf("\n\n");
        }
  }




  Output: (Singly Linked List Example)
  jp@jp-VirtualBox:$ ./a.out
  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:1
  Enter data to insert into list
  10

   ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:1
  Enter data to insert into list
  20

   ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:2
  Enter data to insert into list
  30

   ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:9
  +--------------------------------+
  |Node[1] addr: 157687832   |
  +--------------------------------+
  |data =  20                        |
  +--------------------------------+
  |next =  157687816             |
  +--------------------------------+
                  || 
                  || 
                  \/ 
  +--------------------------------+
  |Node[2] addr: 157687816   |
  +--------------------------------+
  |data =  10                        |
  +--------------------------------+
  |next =  157687848             |
   +-------------------------------+
                 || 
                 || 
                 \/ 
  +--------------------------------+
  |Node[3] addr: 157687848   |
  +--------------------------------+
  |data =  30                         |
  +--------------------------------+
  |next =          0                  |
  +--------------------------------+

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:3
  Enter value for position and data
  2 40

   ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:9
  +--------------------------------+
  |Node[1] addr: 157687832   |
  +--------------------------------+
  |data =  20                        |
  +--------------------------------+
  |next =  157687864             |
  +--------------------------------+
                 || 
                 || 
                 \/ 
  +--------------------------------+
  |Node[2] addr: 157687864   |
  +--------------------------------+
  |data =  40                        |
  +--------------------------------+
  |next =  157687816             |
  +--------------------------------+
                || 
                || 
                \/ 
  +--------------------------------+
  |Node[3] addr: 157687816   |
  +--------------------------------+
  |data =  10                        |
  +--------------------------------+
  |next =  157687848             |
  +--------------------------------+
               || 
               || 
               \/ 
  +--------------------------------+
  |Node[4] addr: 157687848   |
  +--------------------------------+
  |data =  30                        |
  +--------------------------------+
  |next =          0                  |
  +--------------------------------+

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:4
  Enter value for data to be searched
  10
  Give node is present in the list-data:10

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:5
  Enter value to get previous value
  10
  Value present previous to 10 is 40

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:6
  Enter value to get next value
  40
  Value present next to 40 is 10

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:7
  Enter value to delete node
  40

   ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:9
  +--------------------------------+
  |Node[1] addr: 157687832   |
  +--------------------------------+
  |data =  20                        |
  +--------------------------------+
  |next =  157687816             |
  +--------------------------------+
                  || 
                  || 
                  \/ 
  +---------------------------------+
   |Node[2] addr: 157687816   |
  +---------------------------------+
  |data =  10                          |
  +---------------------------------+
  |next =  157687848               |
  +---------------------------------+
                  || 
                  || 
                  \/ 
  +--------------------------------+
  |Node[3] addr: 157687848   |
  +--------------------------------+
  |data =  30                        |
  +--------------------------------+
  |next =          0                  |
  +--------------------------------+

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:8

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:10
  List is unavailable

  ########################################
  1. Insertion at the start of List
  2. Insert at the end of list
  3. Insert at node at the given position
  4. Find node
  5. Find Previous data value
  6. Find next data value
  7. Delete node
  8. Delete list
  9. Walk list
  10. Is list exists
  11. Exit
  ########################################
  Enter ur choice:11



Posted by at 11:42

1 comment:

Subscribe to: Post Comments (Atom)