Comparison between Array and Linked List Data Structures
Linked lists and arrays are commonly used data structures in programming. Linked lists offer flexibility in size changes and efficient rearrangement of elements, while arrays provide direct access to elements based on their index. Linked lists involve pointers connecting elements, allowing for dynamic size adjustments. On the other hand, arrays offer fast random access to elements due to their contiguous memory allocation. Each data structure has its advantages and use cases, and understanding their differences is crucial for efficient programming.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Linked List V S ABBIRAMY Asst. Professor Department of Computer Science Spring 2012 Programming and Data Structure 1
Introduction A linked list is a data structure which can change during execution. Successive elements are connected by pointers. Last element points to NULL. It can grow or shrink in size during execution of a program. It can be made just as long as required. It does not waste memory space. head A B C Spring 2012 Programming and Data Structure 2
Introduction Keeping track of a linked list: Must know the pointer to the first element of the list (called start, head, etc.). Linked lists provide flexibility in allowing the items to be rearranged efficiently. Insert an element. Delete an element. Spring 2012 Programming and Data Structure 3
Illustration: Insertion A B C Item to be inserted X tmp A A B C curr X Spring 2012 Programming and Data Structure 4
Pseudo-code for insertion typedef struct nd { struct item data; struct nd * next; } node; void insert(node *curr) { node * tmp; tmp=(node *) malloc(sizeof(node)); tmp->next=curr->next; curr->next=tmp; } Spring 2012 Programming and Data Structure 5
Illustration: Deletion Item to be deleted A B C tmp curr A B C Spring 2012 Programming and Data Structure 6
Pseudo-code for deletion typedef struct nd { struct item data; struct nd * next; } node; void delete(node *curr) { node * tmp; tmp=curr->next; curr->next=tmp->next; free(tmp); } Spring 2012 Programming and Data Structure 7
In essence ... For insertion: A record is created holding the new item. The next pointer of the new record is set to link it to the item which is to follow it in the list. The next pointer of the item which is to precede it must be modified to point to the new item. For deletion: The next pointer of the item immediately preceding the one to be deleted is altered, and made to point to the item following the deleted item. Spring 2012 Programming and Data Structure 8
Array versus Linked Lists Arrays are suitable for: Inserting/deleting an element at the end. Randomly accessing any element. Searching the list for a particular value. Linked lists are suitable for: Inserting an element. Deleting an element. Applications where sequential access is required. In situations where the number of elements cannot be predicted beforehand. Spring 2012 Programming and Data Structure 9
Types of Lists Depending on the way in which the links are used to maintain adjacency, several different types of linked lists are possible. Linear singly-linked list (or simply linear list) One we have discussed so far. head A B C Spring 2012 Programming and Data Structure 10
Circular linked list The pointer from the last element in the list points back to the first element. head A B C Spring 2012 Programming and Data Structure 11
Doubly linked list Pointers exist between adjacent nodes in both directions. The list can be traversed either forward or backward. Usually two pointers are maintained to keep track of the list, head and tail. head tail A B C Spring 2012 Programming and Data Structure 12
Basic Operations on a List Creating a list Traversing the list Inserting an item in the list Deleting an item from the list Concatenating two lists into one Spring 2012 Programming and Data Structure 13
Creating a List Spring 2012 Programming and Data Structure 14
How to begin? To start with, we have to create a node (the first node), and make head point to it. head = (node *) malloc(sizeof(node)); head roll name next age Spring 2012 Programming and Data Structure 15
Contd. If there are n number of nodes in the initial linked list: Allocate n records, one by one. Read in the fields of the records. Modify the links of the records so that the chain is formed. head A B C Spring 2012 Programming and Data Structure 16
Traversing the List Spring 2012 Programming and Data Structure 17
What is to be done? Once the linked list has been constructed and head points to the first node of the list, Follow the pointers. Display the contents of the nodes as they are traversed. Stop when the next pointer points to NULL. Spring 2012 Programming and Data Structure 18
void display (node *head) { int count = 1; node *p; p = head; while (p != NULL) { printf ("\nNode %d: %d %s %d", count, p->roll, p->name, p->age); count++; p = p->next; } printf ("\n"); } Spring 2012 Programming and Data Structure 19
Inserting a Node in a List Spring 2012 Programming and Data Structure 20
How to do? The problem is to insert a node before a specified node. Specified means some value is given for the node (called key). In this example, we consider it to be roll. Convention followed: If the value of roll is given as negative, the node will be inserted at the end of the list. Spring 2012 Programming and Data Structure 21
Contd. When a node is added at the beginning, Only one next pointer needs to be modified. head is made to point to the new node. New node points to the previously first element. When a node is added at the end, Two next pointers need to be modified. Last node now points to the new node. New node points to NULL. When a node is added in the middle, Two next pointers need to be modified. Previous node now points to the new node. New node points to the next node. Spring 2012 Programming and Data Structure 22
void insert (node **head) { int k = 0, rno; node *p, *q, *new; new = (node *) malloc(sizeof(node)); printf ("\nData to be inserted: "); scanf ("%d %s %d", &new->roll, new->name, &new->age); printf ("\nInsert before roll (-ve for end):"); scanf ("%d", &rno); p = *head; if (p->roll == rno) /* At the beginning */ { new->next = p; *head = new; } Spring 2012 Programming and Data Structure 23
else { { q = p; p = p->next; } if (p == NULL) /* At the end */ { q->next = new; new->next = NULL; } else if (p->roll == rno) /* In the middle */ { q->next = new; new->next = p; } } } while ((p != NULL) && (p->roll != rno)) The pointers q and p always point to consecutive nodes. Spring 2012 Programming and Data Structure 24
