Implement a doubly linked list) The MyLinkedList class used in Listing 24.6 is a

Question

Implement a doubly linked list) The MyLinkedList class used in Listing 24.6 is a one-way directional linked list that enables one-way traversal of the list. Modify the Node class to add the new data field name previous to refer to the previous node in the list, as follows:
public class Node<E> {

E element;

Node<E> next;

Node<E> previous;
public Node(E e) {

element = e;

}

}
Implement a new class named TwoWayLinkedList that uses a doubly linked list to store elements. The MyLinkedList class in the text extends MyAbstractList. Define TwoWayLinkedList to extend the java.util.AbstractSequentialList class. You need to implement all the methods defined in MyLinkedList as well as the methods listIterator() and listIterator(int index). Both return an instance of java.util. ListIterator<E>. The former sets the cursor to the head of the list and the latter to the element at the specified index.

Listing 24.6

1 public class MyLinkedList<E> extends MyAbstractList<E> {

2 private Node<E> head, tail;
3
4 /** Create a default list */
5 public MyLinkedList() {
6 }
7
8 /** Create a list from an array of objects */
9 public MyLinkedList(E[] objects) {
10 super(objects);
11 }
12
13 /** Return the head element in the list */
14 public E getFirst() {
15 if (size == 0) {
16 return null;
17 }
18 else {
19 return head.element;
20 }
21 }
22
23 /** Return the last element in the list */
24 public E getLast() {
25 if (size == 0) {
26 return null;
27 }
28 else {
29 return tail.element;
30 }
31 }
32
33 /** Add an element to the beginning of the list */
34 public void addFirst(E e) {
35 // Implemented in Section 24.4.3.1, so omitted here
36 }
37
38 /** Add an element to the end of the list */
39 public void addLast(E e) {
40 // Implemented in Section 24.4.3.2, so omitted here
41 }
42
43 @Override /** Add a new element at the specified index
44 * in this list. The index of the head element is 0 */
45 public void add(int index, E e) {
46 // Implemented in Section 24.4.3.3, so omitted here
47 }
48
49 /** Remove the head node and
50 * return the object that is contained in the removed node. */
51 public E removeFirst() {
52 // Implemented in Section 24.4.3.4, so omitted here
/** Remove the last node and
56 * return the object that is contained in the removed node. */
57 public E removeLast() {
58 // Implemented in Section 24.4.3.5, so omitted here
59 }
60
61 @Override /** Remove the element at the specified position in this
62 * list. Return the element that was removed from the list. */
63 public E remove(int index) {
64 // Implemented earlier in Section 24.4.3.6, so omitted here
65 }
66
67 @Override
68 public String toString() {
69 StringBuilder result = new StringBuilder("[");
70
71 Node<E> current = head;
72 for (int i = 0; i < size; i++) {
73 result.append(current.element);
74 current = current.next;
75 if (current != null) {
76 result.append(", "); // Separate two elements with a comma
77 }
78 else {
79 result.append("]"); // Insert the closing ] in the string
80 }
81 }
82
83 return result.toString();
84 }
85
86 @Override /** Clear the list */
87 public void clear() {
88 size = 0;
89 head = tail = null;
90 }
91
92 @Override /** Return true if this list contains the element e */
93 public boolean contains(E e) {
94 System.out.println("Implementation left as an exercise");
95 return true;
96 }
97
98 @Override /** Return the element at the specified index */
99 public E get(int index) {
100 System.out.println("Implementation left as an exercise");
101 return null;
102 }
103
104 @Override /** Return the index of the head matching element
105 * in this list. Return -1 if no match. */
106 public int indexOf(E e) {
107 System.out.println("Implementation left as an exercise");
108 return 0;
109 }
110
111 @Override /** Return the index of the last matching element
112 * in this list. Return -1 if no match. */
113 public int lastIndexOf(E e) {
114 System.out.println("Implementation left as an exercise");
115 return 0;
116 }
117
118 @Override /** Replace the element at the specified position
119 * in this list with the specified element. */
120 public E set(int index, E e) {
121 System.out.println("Implementation left as an exercise");
122 return null;
123 }
124
125 @Override /** Override iterator() defined in Iterable */
126 public java.util.Iterator<E> iterator() {
127 return new LinkedListIterator();
128 }
129
130 private class LinkedListIterator
131 implements java.util.Iterator<E> {
132 private Node<E> current = head; // Current index
133
134 @Override
135 public boolean hasNext() {
136 return (current != null);
137 }
138
139 @Override
140 public E next() {
141 E e = current.element;
142 current = current.next;
143 return e;
144 }
145
146 @Override
147 public void remove() {
148 System.out.println("Implementation left as an exercise");
149 }
150 }
151
152 // This class is only used in LinkedList, so it is private.
153 // This class does not need to access any
154 // instance members of LinkedList, so it is defined static.
155 private static class Node<E> {
156 E element;
157 Node<E> next;
158
159 public Node(E element) {
160 this.element = element;

Explanation / Answer

package com.itrosys.sarathi.linkedlist;

import java.util.NoSuchElementException;

public class DoublyLinkedListImpl<E> {

private Node head;
private Node tail;
private int size;

public DoublyLinkedListImpl() {
size = 0;
}
/**
* this class keeps track of each element information
* @author java2novice
*
*/
private class Node {
E element;
Node next;
Node prev;

public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
/**
* returns the size of the linked list
* @return
*/
public int size() { return size; }

/**
* return whether the list is empty or not
* @return
*/
public boolean isEmpty() { return size == 0; }

/**
* adds element at the starting of the linked list
* @param element
*/
public void addFirst(E element) {
Node tmp = new Node(element, head, null);
if(head != null ) {head.prev = tmp;}
head = tmp;
if(tail == null) { tail = tmp;}
size++;
System.out.println("adding: "+element);
}

/**
* adds element at the end of the linked list
* @param element
*/
public void addLast(E element) {

Node tmp = new Node(element, null, tail);
if(tail != null) {tail.next = tmp;}
tail = tmp;
if(head == null) { head = tmp;}
size++;
System.out.println("adding: "+element);
}

/**
* this method walks forward through the linked list
*/
public void iterateForward(){

System.out.println("iterating forward..");
Node tmp = head;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.next;
}
}

/**
* this method walks backward through the linked list
*/
public void iterateBackward(){

System.out.println("iterating backword..");
Node tmp = tail;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.prev;
}
}

/**
* this method removes element from the start of the linked list
* @return
*/
public E removeFirst() {
if (size == 0) throw new NoSuchElementException();
Node tmp = head;
head = head.next;
head.prev = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}

/**
* this method removes element from the end of the linked list
* @return
*/
public E removeLast() {
if (size == 0) throw new NoSuchElementException();
Node tmp = tail;
tail = tail.prev;
tail.next = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}

public static void main(String a[]){

DoublyLinkedListImpl<Integer> dll = new DoublyLinkedListImpl<Integer>();
dll.addFirst(10);
dll.addFirst(34);
dll.addLast(56);
dll.addLast(364);
dll.iterateForward();
dll.removeFirst();
dll.removeLast();
dll.iterateBackward();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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