linked list

• Data structure is a way of organizing data items by considering its relationship to each other.
• Data structures affects the design of structural and functional aspects of a program.

Type of Data structures :

1) Primitive DS :

•    Directly operated on by machine instructions .
•    Integers , floating point numbers , characters , strings , pointers.

2) Non - Primitive DS :

•   Arrays 
•   Lists 
• Graph
• Trees
• Files

Linked Lists

• A set of varying number of elements to which insertion and deletion can be made .
• A linear list has elements adjacent to each other.
• Each elements is called node.

    There are two types of linked lists 

Each node must contain :

1. Data saved 
2. Pointer to the next node .
3. Pointer to the previous node.

-------------------------------------------------------------------

Example :

struct node {

struct node *pnext;

struct node *pprev;

int  data ;

}

struct node *phead;

struct node *ptail;

-----------------------------------------------------------------

Operation on Double Linked list :

• Initially a list is empty so phead = ptail.
• Addition
• Insertion
• Deletion
• Search
• Free List

Have the following cases to test in insertion at loc :

•  Empty List 
• LOC = 0 (Same as Insertion at BEGIN )
• LOC out of list (Same as Insertion at END)
• LOC in anywhere in list 

Example :

Implement a program that take integer numbers using linked list and have options of Delete and Display all the list .


Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

#include <stdio.h> #include <stdlib.h> struct node { int data; struct node *pnext; struct node *pprev; }; struct node *ptail; struct node *phead; struct node *createnode(int data); int addnode (int data); struct node *createnode( int data ){ struct node *ptr=NULL; ptr=(struct node*)malloc(sizeof(struct node)); if (ptr){ ptr->data=data; ptr->pnext=ptr->pprev=NULL; } return ptr; } int addnode( int data ){ int flag =0; struct node *ptr=createnode(data ); if (ptr){ flag=1; if(ptail== NULL) ptail=phead=ptr; else{ ptail->pnext=ptr; ptr->pprev=ptail; ptail=ptr;} } return flag; } void display() { struct node *temp; if (phead == NULL) printf ("No elements to print!\n"); else { temp=phead; do { printf ("%d\n", (temp->data)); temp=temp->pnext; } while (temp!=NULL); } } void delet (){ int num; struct node *temp; printf("please enter the data to be deleted:\n"); scanf("%d",&num); if (phead->data == num){ temp = phead; phead=phead->pnext; free(temp);} else if (ptail->data == num){ temp=ptail; ptail=temp->pprev; ptail->pnext=NULL; free(temp); }else { temp =phead; do{ temp=temp->pnext; }while (temp->data !=num); temp=temp->pprev; temp->pnext=temp->pnext->pnext; temp=temp->pnext; temp->pprev=temp->pprev->pprev; free(temp); } } int main() { int choice ; int input ; do { printf("what you want to do ?\n 1-add\n 2-delete\n 3-display\n 4-exit\n "); scanf("%d",&choice); switch(choice) { case 1 : printf("please enter the input intger :\n"); scanf("%d",&input); addnode(input); ;break; case 2 : delet();break; case 3 : display();break; case 4 : break; } }while (choice !=4); return 0; }

Output :

what you want to do ?
 1-add
 2-delete
 3-display
 4-exit
 1
please enter the input intger :
3
what you want to do ?
 1-add
 2-delete
 3-display
 4-exit
 1
please enter the input intger :
4
what you want to do ?
 1-add
 2-delete
 3-display
 4-exit
 1
please enter the input intger :
5
what you want to do ?
 1-add
 2-delete
 3-display
 4-exit
 3
3
4
5
what you want to do ?
 1-add
 2-delete
 3-display
 4-exit
 2
please enter the data to be deleted:
4
what you want to do ?
 1-add
 2-delete
 3-display
 4-exit
 3
3
5
what you want to do ?
 1-add
 2-delete
 3-display
 4-exit
 4

Share this

Unknown