Part 2 Linked List.pdf

Data Structures and Algorithms Part 2: Linked List 1 Data structures and Algorithms Part 2 Outlines  Links in a List.  A Simple Linked List.  Inserting an item at the beginning of the list.  Deleting the item at the beginning of the list.  Iterating throug...

Data Structures and Algorithms Part 2: Linked List 1 Data structures and Algorithms Part 2 Outlines  Links in a List.  A Simple Linked List.  Inserting an item at the beginning of the list.  Deleting the item at the beginning of the list.  Iterating through the list to display its contents.  Finding and Deleting Specified Links.  The find() method.  The delete() method. 2 Data structures and Algorithms Part 2 outlines  Double-Ended Lists  Sorted Lists  Doubly Linked Lists  Traversal the list both forward and backward  Insertion at the beginning  Insertion at an arbitrary location.  Deleting an arbitrary link 3 Data structures and Algorithms Part 2 Links in a List class Link { public int iData; // data public double dData; // data public Link next; // reference to next link } This kind of class definition is sometimes called self-referential because it contains a field—called next in this case—of the same type as itself. 4 Data structures and Algorithms Part 2  A Simple Linked List  The only operations allowed in this version of a list are  Inserting an item at the beginning of the list.  Deleting the item at the beginning of the list.  Iterating through the list to display its contents. 5 Data structures and Algorithms Part 2 A Simple Linked List class Link { public int iData; // data item public double dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(int id, double dd) // constructor { iData = id; // initialize data dData = dd; // (‘next’ is automatically } // set to null) // ------------------------------------------------------------- public void displayLink() // display ourself { System.out.print(“{“ + iData + “, “ + dData + “} “); } } // end class Link 6 Data structures and Algorithms Part 2  The constructor initializes the data. There’s no need to initialize the next field because it’s automatically set to null when it’s created. The null value means it doesn’t refer to anything, which is the situation until the link is connected to other links. 7 Data structures and Algorithms Part 2 The LinkList Class  The LinkList class contains only one data item: a reference to the first link on the list. This reference is called first. class LinkList { private Link first; // ref to first link on list // ------------------------------------------------------------- public void LinkList() // constructor { first = null; // no items on list yet } // ------------------------------------------------------------- public boolean isEmpty() // true if list is empty { return (first==null); } // ------------------------------------------------------------- //... other methods go here } 8 Data structures and Algorithms Part 2 The insertFirst() Method 9 Data structures and Algorithms Part 2  The insertFirst() Method  In insertFirst() we begin by creating the new link using the data passed as arguments. Then we change the link references // insert at start of list public void insertFirst(int id, double dd) { // make new link Link newLink = new Link(id, dd); newLink.next = first; // newLink --> old first first = newLink; // first --> newLink } 10 Data structures and Algorithms Part 2 The deleteFirst() Method 11 Data structures and Algorithms Part 2 The deleteFirst() Method  The deleteFirst() method is the reverse of insertFirst(). It disconnects the first link by rerouting first to point to the second link. This second link is found by looking at the next field in the first link: public Link deleteFirst() // delete first item { // (assumes list not empty) Link temp = first; // save reference to link first = first.next; // delete it: first-->old next return temp; // return deleted link } 12 Data structures and Algorithms Part 2  The displayList() Method  To display the list, you start at first and follow the chain of references from link to link. A variable current points to each link in turn. It starts off pointing to first, which holds a reference to the first link. The statement current = current.next; changes current to point to the next link because that’s what’s in the next field in each link. Here’s the entire displayList() method: 13 Data structures and Algorithms Part 2 public void displayList() { System.out.print(“List (first-->last): “); Link current = first; // start at beginning of list while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } System.out.println(“”); } 14 Data structures and Algorithms Part 2 Stepping along the list 15 Data structures and Algorithms Part 2  Finding Specified Links  The find() method The find() method works much like the displayList() method. The reference current initially points to first and then steps its way along the links by setting itself repeatedly to current.next. At each link, find() checks whether that link’s key is the one it’s looking for. If the key is found, it returns with a reference to that link. If find() reaches the end of the list without finding the desired link, it returns null. 16 Data structures and Algorithms Part 2 The find() method public Link find(int key) // find link with given key { // (assumes non-empty list) Link current = first; // start at ‘first’ while(current.iData != key) // while no match, { if(current.next == null) // if end of list, return null; // didn’t find it else // not end of list, current = current.next; // go to next link } return current; // found it } 17 Data structures and Algorithms Part 2 Deleting Specified Links  The delete() method The delete() method is similar to find() in the way it searches for the link to be deleted. However, it needs to maintain a reference not only to the current link (current), but to the link preceding the current link (previous). It does so because, if it deletes the current link, it must connect the preceding link to the following link 18 Data structures and Algorithms Part 2 The delete() method 19 Data structures and Algorithms Part 2 public Link delete(int key) // delete link with given key { // (assumes non-empty list) Link current = first; // search for link Link previous = first; while(current.iData != key) { if(current.next == null) return null; // didn’t find it else { previous = current; // go to next link current = current.next; } } // found it if(current == first) // if first link, first = first.next; // change first else // otherwise, previous.next = current.next; // bypass it return current; } 20 Data structures and Algorithms Part 2  All codes for double- ended lists reference Double-Ended Lists pages 198-201  A double-ended list is similar to an ordinary linked list, but it has one additional feature: a reference to the last link as well as to the first. The reference to the last link permits you to insert a new link directly at the end of the list as well as at the beginning. 21 Data structures and Algorithms Part 2  All codes for sorted list reference pages 212-217 Sorted Lists  The advantages of a sorted list over a sorted array are speed of insertion (because elements don’t need to be moved) and the fact that a list can expand to fill available memory, while an array is limited to a fixed size. However, a sorted list is somewhat more difficult to implement than a sorted array.  To insert an item in a sorted list, the algorithm must first search through the list until it finds the appropriate place to put the item. 22 Data structures and Algorithms Part 2  All codes doubly linked-list Doubly Linked Lists reference pages 221-231 Each link has two references to other links instead of one. The first is to the next link, as in ordinary lists. The second is to the previous link. So we can: Insert a node in any position Delete a node from any position Traverse the list forward and backward 23 Data structures and Algorithms Part 2  class Link { public long dData; // data item public Link next; // next link in list public Link previous; // previous link in list... } 24 Data structures and Algorithms Part 2  Traversal of a Doubly Linked Lists  Two display methods demonstrate traversal of a doubly linked list. The displayForward() method is the same as the displayList() method we’ve seen in ordinary linked lists. The displayBackward() method is similar but starts at the last element in the list and proceeds toward the start of the list, going to each element’s previous field. 25 Data structures and Algorithms Part 2  Insertion at the beginning if (isEmpty) { first=newlink; last=newlink; } else { first.previous=newlink; newlink.next=first; first=newlink; } 26 Data structures and Algorithms Part 2  Insertion at an arbitrary location. if(current==last) { newLink.next = null; last = newLink; } else { newLink.next = current.next; current.next.previous = newLink; } newLink.previous = current; current.next = newLink; 27 Data structures and Algorithms Part 2 if (current==first) Deleting an arbitrary link { first=current.next; current.next.previous=null; } else if(current==last) { current.previous.next=null; last=current.previous; } else { current.previous.next=current.next; current.next.previous=current.previous; } 28 Data structures and Algorithms Part 2 Reference  “Data Structures & Algorithms in Java”, 2nd edition 2003, Robert Lafore. (Chapter 5) 29 Data structures and Algorithms Part 2