Page 526 - Computer science 868 Class 12
P. 526

76                           break;
                77                   }

                78               }while(ch>=1&&ch<=3);
                79           }

                80       }
                  13.3  LINKED LIST


              The linked list is a linear data structure that contains a sequence of elements called “Nodes” which are linked to one
              another by reference or memory address. Unlike array, the nodes are not stored at contiguous memory locations. Each
              “Node” consists of two parts: the data part and a link which stores the address of the next node in the list.

                                                  Data                         Link
                                               Actual value            Address of the next node

              A linked list can be of two types:
              1.  Single linked list: In this type, each node stores the address of the next node in the linked list. The address of the
                 first node is stored in a reference node called the header pointer or the start pointer or front pointer. The address
                 of the last node in the list is NULL. In single linked list the traversal is always in the forward direction.
                The diagrammatic representation of a single linked list is shown below.

                                   header 1001



                                   29      1098               18      1156               35       NULL
                                      1001                        1098                       1156
                Here 1001, 1098, 1156 represents memory address.
              2.  Double linked list: In this structure, the linked list has two address parts: one stores the address of the next element
                 of the linked list and the other stores the address of the previous element. The navigation can thus takes place in
                 both forward and backward directions. The pictorial representation is as follows:

                                           Address of            Data             Address of
                                         previous node                            next node



                      Note: Double linked list is beyond the scope of the syllabus and is not discussed further.



              Advantages of Linked List over array
              1.  Array is a static data structure, so the size must be declared at the beginning. In a linked list, memory is allocated
                 dynamically. Thus, a linked list can expand or shrink at run time.
              2.  Since in an array the size is fixed, sometimes memory space remains unutilised. In a linked list, the exact number of
                 memory locations are declared, and therefore, there is no wastage of memory space.
              3.  In an array, the items are stored contiguously in memory. Inserting or deleting any element in an array needs
                 shifting of the successor elements to the right or left respectively. In a linked list, it involves simply breaking the
                 previous link and creating a new one.






                524524  Touchpad Computer Science-XII
   521   522   523   524   525   526   527   528   529   530   531