linked list Group 01, SY-IT-VIT Pune

  Before understanding the linked list concept, we first look at  why there is a need for a linked list. If we want to store the value in a memory, we need a memory manager that manages the memory for every variable. For example, if we want to create a variable of integer type like: int  x;   In the above example, we have created a variable 'x' of type integer. As we know that integer variable occupies 4 bytes, so 'x' variable will occupy 4 bytes to store the value. Suppose we want to create an array of integer type like: int  x[ 3 ];   In the above example, we have declared an array of size 3. As we know, that all the values of an array are stored in a continuous manner, so all the three values of an array are stored in a sequential fashion. The total memory space occupied by the array would be  3*4 = 12 bytes . There are two major drawbacks of using array: We cannot insert more than 3 elements in the above example because only 3 spaces are allocated for 3 elements. In

A Linked List is a linear data structure  which consists of a group of nodes. Unlike an array, it has elements that are stored in random memory locations. Each node contains two fields: data  stored at that particular address. Pointer  which contains the address of the next node. The last node of the Linked list contains a pointer to null to represent the termination of the linked list. Generally, we call the first node as  Head  node and last node as  Tail  node in Linked List. Why Linked List Over Array? Array contains following limitations: The size of an array is fixed. We must know the size of the array  at the time of its creation, hence it is impossible to change its size at runtime. Inserting a new element in an array of elements is expensive because we need to shift elements to create room for new elements to insert. Deleting an element in an array is also expensive as it also takes shifting of elements in the array. Advantages of Linked List: Insertion and deletion operations