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

