Data structure slides of algorithm- 06.ppt

Data structure slides of algorithm- 06.ppt

• 1.
  Lecture # 06 LinkList
• 2.
  Why we usedLink list  One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set.  Arrays are also expensive to maintain new insertions and deletions.  In this lecture we consider another data structure called Linked Lists that addresses some of the limitations of arrays.
• 3.
  Link List  Alinked list is a series of connected nodes  Each node contains at least  A piece of data (any type)  Pointer or address to the next node in the list.  Head: pointer to the first node  The last node points to NULL A  Head B C A data pointer node
• 4.
  Link List
• 5.
  Link List  Eachelement (we will call it a node) of a list is comprising of two items - the data and a reference to the next node.  The last node has a reference to null. The entry point into a linked list is called the head of the list.  It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.
• 6.
  Link List  Alinked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand.  Link list is linear data structure.  Link list is dynamic list i.e the size is not fixed and it will expand during program execution where array is static list.
• 7.
  Types of LinkList There are two types of link list 1. Single Link List/ One way Link list 2. Double Linked list/ Two way link list
• 8.
  1) Single-link list A single linked list is a dynamic data structure consisting of a sequence of nodes, forming a linear ordering.  Each node stores:  Element (data object)  Reference (i.e., address) to the next node Node: Singly-linked list:
• 9.
  Operations on oneWay linked list 1) Traversing operation 2) Insertion operation 3) Deletion operation
• 10.
  1)Algorithm for Linklist Traversing  This algorithm is used to traverse (visit) all element in a given list. Step 1: [Set current pointer as first] Cur=First Step 2:[Starting loop to show all the element] Repeat 3 & 4…….While ( Cur!=Null) Step 3: [Show information ] Write (Cur->data) Step 4: [ Point to a next node] Cur=Cur-> link Step 5: [ Finish] Exit
• 11.
  Node Creation  Nodeis created in C/C++ language using structures.  A simple node structure is given below  struct node { int data; struct node *next; } 1.x
• 12.
  2) Insertion Operation Letus suppose LIST be a one-way link list with N successive nodes and a node insert is to be inserted in a link list. The given node can be inserted in a link list in the following three locations
• 13.
  Insertion Operation….. 1. FRONTInsertion 2. Middle Insertion 3. End Insertion
• 14.
  1) Front Insertion Front insertion is the easiest way to insert node in a link list( means that node is inserted at the first location in a given link list.
• 15.
  Algorithm for FRONTINSERTION  This algorithm is used to insert a node at the start of a one way link list Step 1: [Create a node & assign it address to tmp ] tmp = New Node address Step 2: [Store information ] tmp-> data = x Step 3: [Assign first to insert link ] tmp-> link = first Step 4: [ Set tmp as start] First = tmp Step 5: [ Finish] Exit
• 16.
  2) End insertion This algorithm is used to insert a node at the end of a one way link list Step 1: [Set prev pointer to first node ] Prev= First Step 2: [Starting loop to reach to the end of list ] Repeat step 3…. While ( Prev -> link !=NULL) Step 3: [Update prev pointer] Prev = Prev -> link Step 4: [ Create a node and set it as tmp] tmp = New node Step 5: [ Store information] tmp -> data = x Step 6: [Set tmp link as null ] tmp -> link= NULL Step 7: [ Set prev link as tmp] Prev-> link= tmp Step 8: [ Finish] Exit
• 17.
  Note:  In theabove algorithm step 2 and 3 are used to reach to the end of link list.  When end of list is found then 4,5,6, we create a new node; assign its address to insert pointer, store information and set “insert” pointer to NULL because null link pointer represent the end of link list.
• 18.
  Note:  In step8, we link the new node to the previous node