{"id":31899,"date":"2021-04-20T21:46:32","date_gmt":"2021-04-20T16:16:32","guid":{"rendered":"https:\/\/www.mygreatlearning.com\/blog\/link-in-c\/"},"modified":"2024-11-13T16:21:54","modified_gmt":"2024-11-13T10:51:54","slug":"link-in-c","status":"publish","type":"post","link":"https:\/\/www.mygreatlearning.com\/blog\/link-in-c\/","title":{"rendered":"LINKED LIST IN C++"},"content":{"rendered":"\n

INTRODUCTION -<\/strong>It is a sequence of items (objects) where every item is linked to the next. They are linked to one another through pointers. There are two parts in each node: the first part contains the data, and the second part contains the address of the next node in the linked list. Address part of the node which is connected to next is also called a link. The following Fig. 1. shows a typical example of a node.<\/p>\n\n\n\n

\"\"\/
Fig. 1. Linked List<\/strong><\/figcaption><\/figure>\n\n\n\n

<\/p>\n\n\n\n

\"\"\/
Fig. 2. Linked List representation in Memory<\/strong><\/figcaption><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Fig. 2. shows a schematic diagram of a linked list. Each node is pictured with two parts. The left part of each node contains the data, and the right part represents the address of the next node. There is an arrow that shows that the first node is connected to the next node. <\/p>\n\n\n\n

IMPLEMENTATION OF LINKED LIST<\/strong><\/p>\n\n\n\n

When we say linked list, we are talking about a singly linked list. There are various types of linked lists which we will discuss below, but here we are going to implement a singly linked list. There is a concept of pointer and structure, what structure data type is in C++ language, also, how to access the structure members using that structure variable and pointer.<\/p>\n\n\n\n

First of all, see the logical view of a linked list in Fig. 3, which shows the linked list having three nodes.<\/p>\n\n\n\n

\"\"\/
Fig 3<\/figcaption><\/figure>\n\n\n\n

<\/p>\n\n\n\n

First, we have to create a node. <\/p>\n\n\n\n

Creating a node using a user-defined data type, i.e. structure :<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Also Read: Function overloading in C++<\/a><\/p>\n\n\n\n

TYPES OF LINKED LIST<\/strong><\/p>\n\n\n\n

 We can divide the linked list into the following three types mainly:<\/p>\n\n\n\n

    \n
  1. Singly-linked list<\/li>\n\n\n\n
  2. Doubly linked list<\/li>\n\n\n\n
  3. Circular linked list<\/li>\n<\/ol>\n\n\n\n
      \n
    1. Singly Linked List or One-Way Chain<\/strong><\/li>\n<\/ol>\n\n\n\n

      In a singly linked list, all the nodes are arranged sequentially. A node in the singly linked list consists of two parts: the data part and the link\/address part. The data part of the node stores actual information that is to be represented by the node, while the link or the address part of the node stores the address of its immediate successor.<\/p>\n\n\n\n

      A one-way chain or singly linked list can be traversed in one direction only; that is why it is known as a one-way chain. Fig. 4. shows the linked list.  <\/p>\n\n\n\n

      \"\"\/
      Fig 4<\/figcaption><\/figure>\n\n\n\n

      <\/p>\n\n\n\n

      \"\"\/<\/figure>\n\n\n\n
      \"\"\/<\/figure>\n\n\n\n
        \n
      1. Doubly Linked List<\/strong><\/li>\n<\/ol>\n\n\n\n

        In a singly linked list, as each node contains the next node\u2019s address, it doesn't have any record of its previous node. However, a doubly-linked list will apply in place of a singly linked list. As we also know, each node of the list contains the address of its previous node of the linked list, so we can find all the details about the previous node by using the previous address stored inside the previous part of each node in a linked list.<\/p>\n\n\n\n

           Every node in the doubly linked list has three fields that are Left_Pointer, Right_Pointer and Data. Fig.5 shows a doubly linked list.<\/p>\n\n\n\n

        \"\"\/<\/figure>\n\n\n\n

        the point will point to the node on the left side (or previous node) that will hold the previous node\u2019s address in a doubly-linked list. RPoint will point the right side (or next node) to the next node\u2019s address in a linked list. Data will store the information of the node.<\/p>\n\n\n\n

        \"\"\/<\/figure>\n\n\n\n

        Representation of Doubly Linked List<\/strong><\/p>\n\n\n\n

        \"\"\/<\/figure>\n\n\n\n
          \n
        1. Circular Linked List<\/strong><\/li>\n<\/ol>\n\n\n\n

          A circular linked list is one where there is no beginning and no end. A singly linked list can be made a circular linked list by simply storing the address of the first node in the linked field of the last node in a linked list. A circular linked list is shown in Fig. 6<\/p>\n\n\n\n

          \"\"\/<\/figure>\n\n\n\n
          \"\"\/<\/figure>\n\n\n\n

          We can traverse a circular linked list until we reach the same node from where we started.<\/p>\n\n\n\n

          There is no null value present in any of the nodes in a circular linked list.<\/p>\n\n\n\n

          OPERATIONS ON LINKED LIST<\/strong><\/p>\n\n\n\n

          The operations performed on the Linked List are as follows:<\/p>\n\n\n\n

            \n
          1. Creation<\/li>\n\n\n\n
          2. Insertion <\/li>\n\n\n\n
          3. Deletion <\/li>\n\n\n\n
          4. Traversing<\/li>\n\n\n\n
          5. Searching <\/li>\n\n\n\n
          6. Concatenation<\/li>\n<\/ol>\n\n\n\n

            Creation<\/em><\/strong> operation is used to create a node or linked list. When a linked list is created with one node, an insertion operation is used to add more elements to the node.<\/p>\n\n\n\n

            Insertion <\/em><\/strong>operation is used to insert a new node at any location in the linked list. A new node may be inserted:<\/p>\n\n\n\n

              \n
            1. At the beginning of the linked list<\/li>\n\n\n\n
            2. At the end of the linked list<\/li>\n\n\n\n
            3. At any position in a linked list<\/li>\n<\/ol>\n\n\n\n

              Deletion <\/em><\/strong>operation is used to delete or remove a node from the linked list. A node may be deleted from the<\/p>\n\n\n\n

                \n
              1. Beginning of a linked list <\/li>\n\n\n\n
              2. End of a linked list<\/li>\n\n\n\n
              3. Specified location of the linked list<\/li>\n<\/ol>\n\n\n\n

                Traversing<\/em><\/strong> <\/em>is the process of going through each node from one end to another end of a linked list. In a singly linked list, we can visit from left to right, forward traversing, but we can not go from right to left. In a doubly-linked list, both side traversing is possible.<\/p>\n\n\n\n

                Concatenation <\/em><\/strong>is the process of appending the second list to the end of the first list in a linked list. Let us consider a list A having n nodes and B with m nodes. Then the concatenation will place the 1st<\/sup> node of B in the (n+1)th node in list A. After concatenation, A will contain (n+m) nodes in the list.<\/p>\n\n\n\n

                EXAMPLES:<\/strong><\/p>\n\n\n\n

                OPERATIONS ON SINGLY LINKED LIST<\/strong><\/p>\n\n\n\n

                                 Some operations can be performed on a singly linked list. A list of all the operations is   given below.<\/p>\n\n\n\n

                Node Creation<\/strong><\/p>\n\n\n\n

                \"\"\/<\/figure>\n\n\n\n

                INSERTION <\/strong><\/p>\n\n\n\n

                  \n
                1. Insertion in a singly linked list<\/strong>: <\/li>\n<\/ol>\n\n\n\n

                  There are the following steps to insert a new node in the list. <\/p>\n\n\n\n

                  \u2022 Allocate the space for the new node and store data into the data part of the node in the singly linked list. <\/p>\n\n\n\n

                  \u2022 ptr = (struct node *) malloc(sizeof(struct node *)); o ptr \u2192 data = item <\/p>\n\n\n\n

                  \u2022 Now, link part of the new node pointing to the first node of the list. <\/p>\n\n\n\n

                   \u2022 ptr->next = head; <\/p>\n\n\n\n

                  \u2022 Now, at last, we need to make the new node the first node of the list <\/p>\n\n\n\n

                   \u2022 head = ptr; <\/p>\n\n\n\n

                  Algorithm <\/strong><\/p>\n\n\n\n

                  STEP-1: IF PTR = NULL <\/p>\n\n\n\n

                  Write OVERFLOW<\/p>\n\n\n\n

                   Go to STEP-7<\/p>\n\n\n\n

                  ELSE<\/p>\n\n\n\n

                  STEP-2: SET NEW_NODE = PTR <\/p>\n\n\n\n

                  STEP-3: SET PTR = PTR \u2192 NEXT <\/p>\n\n\n\n

                  STEP-4: SET NEW_NODE \u2192 DATA = VAL <\/p>\n\n\n\n

                  STEP-5: SET NEW_NODE \u2192 NEXT = HEAD<\/p>\n\n\n\n

                   STEP-6: SET HEAD = NEW_NODE <\/p>\n\n\n\n

                  STEP-7: EXIT<\/p>\n\n\n\n

                  \"\"\/<\/figure>\n\n\n\n

                  DELETION <\/strong><\/p>\n\n\n\n

                  Deletion in a singly linked list:<\/strong><\/p>\n\n\n\n

                  Deleting a node from the beginning of the list is the simplest operation of all the operations. Since the first node of the list is to be deleted, we have to make the head and point to the next of the head.<\/p>\n\n\n\n

                   \u2022 ptr = head;<\/p>\n\n\n\n

                   \u2022 head = ptr->next; <\/p>\n\n\n\n

                   \u2022 The pointer ptr pointing to the head node is now free.  <\/p>\n\n\n\n

                   \u2022 free(ptr)<\/p>\n\n\n\n

                  Algorithm <\/strong><\/p>\n\n\n\n

                  STEP-1: IF HEAD = NULL<\/p>\n\n\n\n

                   Write UNDERFLOW<\/p>\n\n\n\n

                   Go to STEP-5 [END OF IF] <\/p>\n\n\n\n

                  STEP-2: SET PTR = HEAD <\/p>\n\n\n\n

                  STEP-3: SET HEAD = HEAD -> NEXT <\/p>\n\n\n\n

                  STEP-4: FREE PTR <\/p>\n\n\n\n

                  STEP-5: EXIT<\/p>\n\n\n\n

                  \"\"\/<\/figure>\n\n\n\n
                  \"\"\/<\/figure>\n\n\n\n

                  Traversing in a singly linked list <\/strong><\/p>\n\n\n\n

                  Traversing means visiting each node of the list when we perform operations on that. <\/p>\n\n\n\n

                   ptr = head;<\/p>\n\n\n\n

                   while (ptr!=NULL)<\/p>\n\n\n\n

                   {<\/p>\n\n\n\n

                   ptr = ptr -> next;<\/p>\n\n\n\n

                   }<\/p>\n\n\n\n

                   Algorithm<\/strong><\/p>\n\n\n\n

                   STEP-1: SET PTR = HEAD <\/p>\n\n\n\n

                  STEP-2: IF PTR = NULL <\/p>\n\n\n\n

                  WRITE \"EMPTY LIST\" <\/p>\n\n\n\n

                  GOTO STEP-7 <\/p>\n\n\n\n

                  END OF IF <\/p>\n\n\n\n

                  STEP-4: REPEAT STEP-5 AND 6 UNTIL PTR == NULL <\/p>\n\n\n\n

                  STEP-5: PRINT PTR\u2192 DATA <\/p>\n\n\n\n

                  STEP-6: PTR = PTR \u2192 NEXT <\/p>\n\n\n\n

                  [END OF LOOP] <\/p>\n\n\n\n

                  STEP-7: EXIT<\/p>\n\n\n\n

                  Searching in a singly linked list <\/strong><\/p>\n\n\n\n

                  Searching is used to find the location of a particular item in the list. The searching operation needs traversing through the list. <\/p>\n\n\n\n

                  Algorithm<\/strong><\/p>\n\n\n\n

                   STEP-1: SET PTR = HEAD <\/p>\n\n\n\n

                  STEP-2: Set I = 0 <\/p>\n\n\n\n

                  STEP-3: IF PTR = NULL <\/p>\n\n\n\n

                  WRITE \"EMPTY LIST\" <\/p>\n\n\n\n

                  GOTO STEP-8 <\/p>\n\n\n\n

                  END OF IF <\/p>\n\n\n\n

                  STEP-4: REPEAT STEP-5 TO 7 UNTIL PTR == NULL <\/p>\n\n\n\n

                  STEP-5: if ptr \u2192 data = item write i+1 End of IF <\/p>\n\n\n\n

                  STEP-6: I = I + 1 <\/p>\n\n\n\n

                  STEP-7: PTR = PTR \u2192 NEXT <\/p>\n\n\n\n

                  [END OF LOOP] <\/p>\n\n\n\n

                  STEP-8: EXIT<\/p>\n\n\n\n

                  OPERATIONS ON DOUBLY LINKED LIST:<\/strong><\/p>\n\n\n\n

                  Node Creation<\/strong><\/p>\n\n\n\n

                  \"\"\/<\/figure>\n\n\n\n

                  INSERTION<\/strong><\/p>\n\n\n\n

                  Insertion in a doubly-linked list:<\/strong><\/p>\n\n\n\n

                   In the doubly linked list, each node of the list contains double pointers.<\/p>\n\n\n\n

                  Algorithm<\/strong><\/p>\n\n\n\n

                  STEP-1: <\/strong>IF ptr = NULL Write OVERFLOW<\/p>\n\n\n\n

                  Go to STEP-9 [END OF IF]<\/p>\n\n\n\n

                  STEP-2: <\/strong>SET NEW_NODE = ptr<\/p>\n\n\n\n

                  STEP-3: <\/strong>SET ptr = ptr -> NEXT<\/p>\n\n\n\n

                  STEP-4: <\/strong>SET NEW_NODE -> DATA = VAL<\/p>\n\n\n\n

                  STEP-5: <\/strong>SET NEW_NODE -> PREV = NULL STEP-6: <\/strong>SET NEW_NODE -> NEXT = START STEP-7: <\/strong>SET head -> PREV = NEW_NODE<\/p>\n\n\n\n

                  STEP-8: <\/strong>SET head = NEW_NODE<\/p>\n\n\n\n

                  STEP-9: <\/strong>EXIT<\/p>\n\n\n\n

                  \"\"\/<\/figure>\n\n\n\n

                  DELETION<\/strong><\/p>\n\n\n\n

                  Deletion in a doubly-linked list<\/strong><\/p>\n\n\n\n