Data Structures_Linked List

 Definition :  A linked list is a sequence of data structures, which are connected together via links.  Linked List is a sequence of links which contains items.  Each link contains a connection to another link.  Linked list is the second most-used data structure after array.

 Linked List contains a link element called first or head.  HEAD/START gives the address of first node.  Each link carries a data field(s) and a link field called next.  Each link is linked with its next link using its next link.  Last link carries a link as null to mark the end of the list.  Components : ◦ Data Field ◦ Link field

Introduction: Linked list is one of the fundamental data structures, and can be used to implement other data structures. In a linked list there are different numbers of nodes. Each node consists of two fields. The first field holds the value or data and the second fieldholdsthereferencetothenextnodeornull ifthelinkedlistisempty. Data/ Info link/next

1. Static representation using array 2. Dynamic representation using free pool of storage i) Static  Fixed memory allocation  It maintain two arrays: one array for data and other for links Disadvantages of static memory a. If no. of elements is less, remaining locations are wasted. b. Extra memory cannot be allocated. c. If an element has to be inserted, many elements have to be moved.

Definition: Each node in the linked list is created dynamically whenever it is required. Memory space will be allocated for each node as needed while the program is running. 1. Memory can be allotted when ever necessary and hence its efficient. 2. Operations like insertion and deletion are easy since it’s a matter of changing the pointers rather than moving the items themselves. 3. Change in size( growing and shrinking ) is possible during the execution of pgm. 4. Extensive manipulation : Without prior knowledge of memory, operations can be done. 5. Arbitrary memory locations : Memory need not be consecutive.

Dynamic Data Structure  Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memeory. So there is no need to give initial size of linked list. Insertion and Deletion  Insertion and deletion of nodes are really easier.

No Memory Wastage  As size of linked list can increase or decrease at run time so there is no memory wastage. Implementation  Data structures such as stack and queues can be easily implemented using linked list.

Memory Usage  More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself. Traversal  Elements or nodes traversal is difficult in linked list. We can not randomly access any element as we do in array by index. For example if we want to access a node at position n then we have to traverse all the nodes before it. So, time required to access a node is large. Reverse traversing  Reverse traversing in a linked list is very difficult, because it requires more memory for the pointer.

1. Each node requires an extra pointer in addition to information, requiring more space. 2. Insertion or deletion of a node takes a bit longer because it involves more pointer operations. 3. Linked lists do not allow random access. 4. Traversing and changing of pointers consumes a lot of time. 5. Programming is typically trickier with pointers. 6. It is quite difficult to sort elements in a linked list.

 It is used to maintain directory names.  The linked list can perform arithmetic operations in the long integer.  We can also use it to next and previous images in the image viewer.  With the help of the linked list, we can move songs back and forth in the music player.  The linked list is also used for undo in word and Photoshop applications.

Following are the various types of linked list.  Simple/Singly Linked List − Item navigation is forward only.  Doubly Linked List − Items can be navigated forward and backward.  Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.  Circular Doubly Linked List - Items can be navigated forward and backward. Last item contains link of the first element as next and the first element has a link to the last element as previous.

Following are the basic operations supported by a list.  Traverse – Visit all the element in the list  Creation – create the linked list  Insertion − Adds an element at the beginning of the list.  Deletion − Deletes an element at the beginning of the list.  Display − Displays the complete list.  Search − Searches an element using the given key.  Delete − Deletes an element using the given key.

Step1: Create a pointer start to point to the structure called node. struct node *start; Step2: Create a node dynamically i.e. allocate memory for storing this structure using malloc() function. start=(struct node *)malloc(sizeof(struct node)); This statement obtains memory that is sufficient to store a node from free pool and assign the address to the pointer variable start. So this pointer start points to the beginning of the linked list.

 If the created node address is 1101, then start pointer variable contains 1101 and will be pointing to the first node. START 1101 Info link 1101 Step 3: Information and link fields of the node should be given the data. This is done using the following statements. Start->info=20; Start->link=NULL; When link part contains NULL, it means the node does not point to any other node.

Insertion Operation Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted. Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode).

NewNode.next −> RightNode; Now, the next node at the left should point to the new node.

LeftNode.next −> NewNode; This will put the new node in the middle of the two. The new list should look like this −

/* inserts a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); /* 2. put in the data */ new_node->data = new_data; /* 3. Make next of new node as head */ new_node->next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; }

Let LIST be a linked list. Suppose node N is to be inserted between nodes A and B. Before insertion START Node A Node B 2000 2008 2016 START Node A Node B 2000 2008 2016 Node N 2 5 7 X 2000 2 2000 5 7 X 2 2000

 Deletion Operation Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.

 The left (previous) node of the target node now should point to the next node of the target node − LeftNode.next −> TargetNode.next;  This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.

 This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at. TargetNode.next −> NULL;

13. *Using dynamic variables and pointers write a C program to construct a singly linked list consisting of the following information in each node. Roll No (Integer), Name (Character String) .The Operations to be supported are: (a). LINSERT() - Inserting a node(front of the list and after a node) and LDISPLAY() - displaying all the nodes in the linked list. (b). LSEARCH() - Searching a node based on Roll number and LDELETE() - deleting a node based on Roll number. //Linked list #include<stdio.h> #include<string.h> #define null 0 void create(); void display(); void ins_beg();  struct node  {  int rollno;  char name[20];  struct node *link;  };  struct node *start=null,*p,*q,*prev;  void main()  {  int ch,i,regno,pos;  clrscr();  while(1)  {  printf("n1.Create a linked list");  printf("n2.Insert a node in front o  printf("n3.Insert a node at the en  printf("n4.Insert a node at a give  printf("n5.Delete a node based o  printf("n6.Searching for a node b  printf("n7.Display linked list");  printf("n8.Exitn");

 {  case 1:  create();  break;  case 2:  printf("nLinked list before inserting the noden");  display();  ins_beg();  printf("nLinked list after inserting the noden");  display();  break;  case 3:  printf("nLinked list before inserting the noden");  display();  ins_end();  printf("nLinked list after inserting the noden");  display();  break;  case 4:  printf("nLinked list before inserting the noden");  display();  ins_pos();   case 5:  printf("nThe linked list is n");  display();  printf("nEnter the rollno of the node to be deletedn");  scanf("%d",&regno);  del_item(regno);  printf("nLinked list after deletionn");  display();  break;  case 6:  printf("nEnter the rollno to be searched :");  scanf("%d",&regno);  search(regno);  break;  case 7:  display();  break;

 void create()  {  char choice='y';  clrscr();  start=null;  q=null;  while(choice=='y')  {  p=((struct node*)malloc(sizeof(struct node)));  printf("nEnter the rollno & name :");  scanf("%d %s",&p->rollno,p->name);  p->link=null;  if(start==null)  {  start=p;  q=p;  }  else  {  q->link=p;  q=p;  }  printf("nDo you want to create another node y/n :");  choice=getch();  }  }

  void display()  {  printf("nn The nodes in the list arennSTART->");  p=start;  while(p!=null)  {  printf("%d %s ->",p->rollno,p->name);  p=p->link;  }  printf("NULLn");  return;  }

 void ins_beg()  {  p=((struct node*)malloc(sizeof(struct node)));  printf("nEnter register number:");  scanf("%d",&p->rollno);  printf("nEnter name of student:");  scanf("%s",&p->name);  p->link=start;  start=p;  }

 void ins_end()  {  p=(struct node *)malloc(sizeof(struct node));  printf("nEnter register number:");  scanf("%d",&p->rollno);  printf("nEnter name of student:");  scanf("%s",&p->name);  p->link=null;  if(start==null)  {  start=p;  }  else  {  q=start;  while(q->link!=null)  {  q=q->link;  }  q->link=p;  }   }

 void ins_pos()  {  int i,pos;  printf("nEnter the position at which you want to insert the new node:");  scanf("%d",&pos);  if(pos==1)  ins_beg();  else  {  q=start;  for(i=1;i<pos-1;i++)  {  q=q->link;  }  p=(struct node *)malloc(sizeof(struct node));  printf("nEnter register number:");  scanf("%d",&p->rollno);  printf("nEnter name of student:");  scanf("%s",&p->name);  p->link=q->link;  q->link=p;  }   }

 void del_item(int regno)  {  p=start;  prev=null;  if(start==null)  {  printf("nLinked list is emptyn");  return;  }  if(start->rollno==regno)  {  start =start->link;  free(p);  return;  }  while((p->rollno!=regno)&&(p!=null))  {  prev=p;  p=p->link;  }  if(p==null)  printf("nRegister number %d is not found in the linked listn",regno);  else  {  prev->link=p->link;  free(p);   }  }

 void search(int regno)  {  int i=0;  p=start;  while(p!=null)  {  if(regno==p->rollno)  {  i++;  printf("nRoll no %d is found at %d",p->rollno,i);  printf("n Name:%s",p->name);  return;  }  else  {  p=p->link;  i++;  }  }  printf("nNode with register number %d does not exist",regno);  }

 Doubly linked list is a type of linked list in which each node apart from storing its data has two links.  The first link points to the previous node in the list and the second link points to the next node in the list.  The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.

 Implementation of Doubly Linked List First we define the node. struct node { int data; // Data node *prev; // A reference to the previous node node *next; // A reference to the next node };

Now we define our class Doubly Linked List. It has the following methods:  add_front: Adds a new node in the beginning of list  add_after: Adds a new node after another node  add_before: Adds a new node before another node  add_end: Adds a new node in the end of list  delete: Removes the node  forward_traverse: Traverse the list in forward direction  backward_traverse: Traverse the list in backward direction

 A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the following image.

 Deletion in doubly linked list at the end Step 1: IF HEAD = NULL Write UNDERFLOW Go to Step 7 [END OF IF] Step 2: SET TEMP = HEAD Step 3: REPEAT STEP 4 WHILE TEMP->NEXT != NULL Step 4: SET TEMP = TEMP->NEXT [END OF LOOP] Step 5: SET TEMP ->PREV-> NEXT = NULL Step 6: FREE TEMP Step 7: EXIT

Advantages: i) Every node is accessible from a given node. Node can be reached by merely chaining the list. ii) Concatenation and splitting operations are more efficient. iii) One can traverse the list in both the directions. iv) Insertions and deletions are easy. v) It is used to represent trees. Disadvantages: i) Extra memory is required to store next node and previous node address.

 A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element.

Operations In a circular linked list, we perform the following operations...  Insertion  Deletion  Display

Step 1: IF PTR = NULL Write OVERFLOW Go to Step 11 [END OF IF] Step 2: SET NEW_NODE = PTR Step 3: SET PTR = PTR -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET TEMP = HEAD Step 6: Repeat Step 8 while TEMP -> NEXT != HEAD Step 7: SET TEMP = TEMP -> NEXT [END OF LOOP] Step 8: SET NEW_NODE -> NEXT = HEAD Step 9: SET TEMP → NEXT = NEW_NODE Step 10: SET HEAD = NEW_NODE Step 11: EXIT

 Deletion in Circular singly linked list at the end Algorithm Step 1: IF HEAD = NULL Write UNDERFLOW Go to Step 8 [END OF IF] Step 2: SET PTR = HEAD Step 3: Repeat Steps 4 and 5 while PTR -> NEXT != HEAD Step 4: SET PREPTR = PTR Step 5: SET PTR = PTR -> NEXT [END OF LOOP] Step 6: SET PREPTR -> NEXT = HEAD Step 7: FREE PTR Step 8: EXIT

 Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node.  Circular doubly linked list doesn't contain NULL in any of the node.  The last node of the list contains the address of the first node of the list.  The first node of the list also contain address of the last node in its previous pointer.

Algorithm Step 1: IF PTR = NULL Write OVERFLOW Go to Step 13 [END OF IF] Step 2: SET NEW_NODE = PTR Step 3: SET PTR = PTR -> NEXT Step 4: SET NEW_NODE -> DATA = VAL Step 5: SET TEMP = HEAD Step 6: Repeat Step 7 while TEMP -> NEXT != HEAD Step 7: SET TEMP = TEMP -> NEXT [END OF LOOP] Step 8: SET TEMP -> NEXT = NEW_NODE Step 9: SET NEW_NODE -> PREV = TEMP Step 1 : SET NEW_NODE -> NEXT = HEAD Step 11: SET HEAD -> PREV = NEW_NODE Step 12: SET HEAD = NEW_NODE Step 13: EXIT

Algorithm Step 1: IF HEAD = NULL Write UNDERFLOW Go to Step 8 [END OF IF] Step 2: SET TEMP = HEAD Step 3: Repeat Step 4 while TEMP -> NEXT != HEAD Step 4: SET TEMP = TEMP -> NEXT [END OF LOOP] Step 5: SET TEMP -> PREV -> NEXT = HEAD Step 6: SET HEAD -> PREV = TEMP -> PREV Step 7: FREE TEMP Step 8: EXIT

Data Structures_Linked List

More Related Content

Similar to Data Structures_Linked List

More from ThenmozhiK5

Recently uploaded

Data Structures_Linked List