COP 3538 Data Structures with OOPDoubly Linked ListsConsider: Code for class LinkPowerPoint PresentationSlide 5Inserting into a Doubly-Linked list.Deleting a link from a Doubly-Linked listDeletion in a doubly-linked listSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 161COP 3538 Data Structures with OOP Chapter 5 - Part 3Linked ListsDoubly-Linked Lists2Doubly Linked ListsHow do we track in singly-linked lists? Sequence: previous = current; current = current.next;Always keep ‘last’ link for insert() and delete(), etc…So far: a given link has its data and a forward link!Many applications require both forward and rearward traversal of a linked list.To do this, each link (node) has both forward and rearward (backward) links (pointers).So, if we are ‘at’ a given link, can go in either way.3Consider: Code for class Linkclass Link { public long dData; // data item(// other instance data for this object as required.) public Link next; //next link in list (forward) public Link previous; //previous link in list (back) } Downside: each time you insert() a link, one MUST account for two pointers: one to the next link and one to the rear link.Inserting and Deleting can be complicated.One MUST keep track of the links and change them in a prescribed order (we shall see).4 null22; 2.99first null22; 2.99first 44 4.99 null22; 2.99first 44 4.99 66; 6.99Conceptual: Doubly-Linked ListnullnullnullThese may also be double-ended too (not shown)(Can start at both the beginning and end of the linked list.Note: Here we are using an insertFirst() method.5 null22; 2.99first null22; 2.99first 44 4.99 null22; 2.99first 44 4.99Using Memory Addresses – Doubly-Linked List5A45A45A45A45A46B85AC5AC5AC5ACnull6B8Nullnull5ACFirst: find out where the link should be located in list. Search to find. Found. Sequence is important! Fill in links in the new cell first! Remember, you are pointing at 5A4 when you start. So, you have all necessary addresses to do job. To add the links to 6B8, we had to move forward link of 5AC to forward link of 6B8 and backward link of 5A4 to the backward link of 6B8 (the new node). New node is now done.Next, change the forward link in 5AC (which was 5A4) to point to the new link at 6B8, and change backward link in 5A4 (which was 5AC) to point to the new link 6B8. (Four links are involved; two in new node and two changes)Next, we inserted a new first link.We used insertFirst() method.First: we will insert new link at front of list. Allocated link (newLink) is ‘at’ 5AC.Now insert another link whereindicated. The link itself is at 6B8We used an insertAfter() method.. 33 3.995A46B85AC6Inserting into a Doubly-Linked list.Now, as shown, one may need to insert ‘before’ or insert ‘after’ a link somewhere in the list;Also, one may have to insert at the ‘beginning’ of list or the ‘end’ of the list.You will almost always have to searc h to discover where you will insert a new link.If you are inserting at the beginning or end, insertFirst() and insertLast() are easy. To insert elsewhere (assumes links are ‘ordered’), you will have to search to determine the correct location.7Deleting a link from a Doubly-Linked listMust search for link to be deleted.Code for Boundary Conditions:May be at front of listMay be last link of listMay be in betweenMay be not found.Code for Expected Condition: May be in the middle somewhere in linked list.Code for the Boundary Conditions.Your code must account for all of these!8Deletion in a doubly-linked list null22; 2.99first 44 4.995A46B85AC6B4 null6B8Let’s delete this link. 33 3.995A46B85ACTo remove 6B8,Move the forward link in 6B8 (which is 5A4) to the forward link at 5AC. Move the rearward link of 6B8 (which is 5AC) to the rearward link of 5A4You have ‘delinked’ the node to be deleted. null22; 2.99 44 4.995A46B85ACnull6B8 33 3.995A46B85AC5A45ACYields:the graphic: Note: there is no forwardor backward link to 6B8…9class Link { public long dData; // data item public <whatever additional attributes your app requires> public Link next; // next link in list public Link previous; // previous link in list// ------------------------------------------------------------- public Link(long d) // constructor; initializes attributes… { dData = d; } // end constructor// ------------------------------------------------------------- public void displayLink() // display this link { System.out.print(dData + " "); } // probably uses a toString…// ------------------------------------------------------------- } // end class LinkConsider: Code for class Link10class DoublyLinkedList { private Link first; // ref to first item private Link last; // ref to last itempublic DoublyLinkedList() // constructor HERE’S YOUR LINKED LIST. WORKER OBJECT !! { NOTE WHERE THE LINKED LIST IS CREATED! first = null; // no items on list yet NOTE: NO ‘ARRAY’ OF OBJECTS. WHY??? last = null; }public boolean isEmpty() // true if no links { return first==null; }public void insertFirst(long dd) { // if insert at front of list. NO SEARCH!! Link newLink = new Link(dd); // make new link Go through this! if( isEmpty() ) // if empty list, last = newLink; // (Points to end of list, which is new node: newLink) else { first.previous = newLink; // newLink.next = first; // (Points to next link) } first = newLink; // (Points to start of Linked List) }// end insertFirst()public void insertLast(long dd) { // insert at end of list NO SEARCH!!!! Link newLink = new Link(dd); // make new link if( isEmpty() ) // if empty list, first = newLink; // first --> newLink else { last.next = newLink; // old last --> newLink Draw these or at least go through these! newLink.previous = last; // old last <-- newLink We will go through this… } last = newLink; // newLink <-- last }//
View Full Document
Unlocking...