1. Modify the doubly linked list code in Listing 5.8 so that it becomes an order

Question

1. Modify the doubly linked list code in Listing 5.8 so that it becomes an ordered linked list. Besides the
constructor, the DoublyLinkedList class should have the following methods: isEmpty(), insert(),
deleteKey(), and displayForward(). Please test your code of the ordered DoublyLinkedList.

Based upon the Task 1 above, add a new method to the ordered DoublyLinkedList: binarySearch() which
returns the position of the Link object that has a matching key, or -1 if nothing is found. The position of a
Link object is the number of Link object from the first, with the first being zero (0), the second being one
(1), and so forth. Please note that the binarySearch() must be implemented using the binary search
algorithm. Please test your code.
What is the estimated time complexity of your binary search algorithm in terms of Big-O notation? Is it
better than O(logN)? Please explain why.

Code:

// doublyLinked.java
// demonstrates doubly-linked list
// to run this program: C>java DoublyLinkedApp
////////////////////////////////////////////////////////////////
class Link
{
public long dData; // data item
public Link next; // next link in list
public Link previous; // previous link in list
// -------------------------------------------------------------
public Link(long d) // constructor
{ dData = d; }
// -------------------------------------------------------------
public void displayLink() // display this link
{ System.out.print(dData + " "); }
// -------------------------------------------------------------
} // end class Link
////////////////////////////////////////////////////////////////
class DoublyLinkedList
{
private Link first; // ref to first item
private Link last; // ref to last item
// -------------------------------------------------------------
public DoublyLinkedList() // constructor
{
first = null; // no items on list yet
last = null;
}
// -------------------------------------------------------------
public boolean isEmpty() // true if no links
{ return first==null; }
// -------------------------------------------------------------
public void insertFirst(long dd) // insert at front of list
{
Link newLink = new Link(dd); // make new link

if( isEmpty() ) // if empty list,
last = newLink; // newLink <-- last
else
first.previous = newLink; // newLink <-- old first
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}
// -------------------------------------------------------------
public void insertLast(long dd) // insert at end of list
{
Link newLink = new Link(dd); // make new link
if( isEmpty() ) // if empty list,
first = newLink; // first --> newLink
else
{
last.next = newLink; // old last --> newLink
newLink.previous = last; // old last <-- newLink
}
last = newLink; // newLink <-- last
}
// -------------------------------------------------------------
public Link deleteFirst() // delete first link
{ // (assumes non-empty list)
Link temp = first;
if(first.next == null) // if only one item
last = null; // null <-- last
else
first.next.previous = null; // null <-- old next
first = first.next; // first --> old next
return temp;
}
// -------------------------------------------------------------
public Link deleteLast() // delete last link
{ // (assumes non-empty list)
Link temp = last;
if(first.next == null) // if only one item
first = null; // first --> null
else
last.previous.next = null; // old previous --> null
last = last.previous; // old previous <-- last
return temp;
}
// -------------------------------------------------------------
// insert dd just after key
public boolean insertAfter(long key, long dd)
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return false; // didn't find it
}
Link newLink = new Link(dd); // make new link

if(current==last) // if last link,
{
newLink.next = null; // newLink --> null
last = newLink; // newLink <-- last
}
else // not last link,
{
newLink.next = current.next; // newLink --> old next
// newLink <-- old next
current.next.previous = newLink;
}
newLink.previous = current; // old current <-- newLink
current.next = newLink; // old current --> newLink
return true; // found it, did insertion
}
// -------------------------------------------------------------
public Link deleteKey(long key) // delete item w/ given key
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return null; // didn't find it
}
if(current==first) // found it; first item?
first = current.next; // first --> old next
else // not first
// old previous --> old next
current.previous.next = current.next;

if(current==last) // last item?
last = current.previous; // old previous <-- last
else // not last
// old previous <-- old next
current.next.previous = current.previous;
return current; // return value
}
// -------------------------------------------------------------
public void displayForward()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning
while(current != null) // until end of list,
{
current.displayLink(); // display data
current = current.next; // move to next link
}
System.out.println("");
}
// -------------------------------------------------------------
public void displayBackward()
{
System.out.print("List (last-->first): ");
Link current = last; // start at end
while(current != null) // until start of list,
{
current.displayLink(); // display data
current = current.previous; // move to previous link
}
System.out.println("");
}
// -------------------------------------------------------------
} // end class DoublyLinkedList
////////////////////////////////////////////////////////////////
class DoublyLinkedApp
{
public static void main(String[] args)
{ // make a new list
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(22); // insert at front
theList.insertFirst(44);
theList.insertFirst(66);

theList.insertLast(11); // insert at rear
theList.insertLast(33);
theList.insertLast(55);

theList.displayForward(); // display list forward
theList.displayBackward(); // display list backward

theList.deleteFirst(); // delete first item
theList.deleteLast(); // delete last item
theList.deleteKey(11); // delete item with key 11

theList.displayForward(); // display list forward

theList.insertAfter(22, 77); // insert 77 after 22
theList.insertAfter(33, 88); // insert 88 after 33

theList.displayForward(); // display list forward
} // end main()
} // end class DoublyLinkedApp
////////////////////////////////////////////////////////////////

Explanation / Answer

/* * Java Program to Implement Sorted Doubly Linked List */ import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { next = null; prev = null; data = 0; } /* Constructor */ public Node(int d, Node n, Node p) { data = d; next = n; prev = p; } /* Function to set link to next node */ public void setLinkNext(Node n) { next = n; } /* Function to set link to previous node */ public void setLinkPrev(Node p) { prev = p; } /* Funtion to get link to next node */ public Node getLinkNext() { return next; } /* Function to get link to previous node */ public Node getLinkPrev() { return prev; } /* Function to set data to node */ public void setData(int d) { data = d; } /* Function to get data from node */ public int getData() { return data; } } /* Class linkedList */ class linkedList { protected Node start; public int size; /* Constructor */ public linkedList() { start = null; size = 0; } /* Function to check if list is empty */ public boolean isEmpty() { return start == null; } /* Function to get size of list */ public int getSize() { return size; } /* Function to insert element */ public void insert(int val) { Node nptr = new Node(val, null, null); Node tmp, ptr; boolean ins = false; if(start == null) start = nptr; else if (val = tmp.getData() && val list.getSize() ) System.out.println("Invalid position "); else list.deleteAtPos(p); break; case 3 : System.out.println("Empty status = "+ list.isEmpty()+" "); break; case 4 : System.out.println("Size = "+ list.getSize() +" "); break; default : System.out.println("Wrong Entry "); break; } /* Display List */ list.display(); System.out.println(" Do you want to continue (Type y or n) "); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } } Sorted Doubly Linked List Test Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 24 Doubly Linked List = 24 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 6 Doubly Linked List = 6 24 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 19 Doubly Linked List = 6 19 24 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 1 Doubly Linked List = 1 6 19 24 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 7 Doubly Linked List = 1 6 7 19 24 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 94 Doubly Linked List = 1 6 7 19 24 94 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 4 Size = 6 Doubly Linked List = 1 6 7 19 24 94 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 1 Doubly Linked List = 6 7 19 24 94 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 3 Doubly Linked List = 6 7 24 94 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 4 Doubly Linked List = 6 7 24 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 1 Doubly Linked List = 7 24 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 2 Doubly Linked List = 7 Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 1 Doubly Linked List = empty Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 4 Size = 0 Doubly Linked List = empty Do you want to continue (Type y or n) y Sorted Doubly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 3 Empty status = true Doubly Linked List = empty Do you want to continue (Type y or n) n

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.