Reputation: 71
I am trying to build a linked list that has a addAfter method. For some reason, the add method will insert a new node, but it wont update the next nodes previous member variable. Here is my output. Notice in the second list, one of the "previous" outputs is not right. How do I fix my addafter method?
public class DoubleLinkedList<E> implements List211<E> {
private static class DLinkedNode<E> {
private E data;
private DLinkedNode<E> next = null;
private DLinkedNode<E> prev = null;
private DLinkedNode(E dataItem) {
data = dataItem;
}
private DLinkedNode(E dataItem, DLinkedNode<E> nextNodeRef,
DLinkedNode<E> prevNodeRef) {
data = dataItem;
next = nextNodeRef;
prev = prevNodeRef;
}
public String toString() {
return data.toString();
}
public void setPrev(DLinkedNode<E> prev) {
this.prev = prev;
}
}
private DLinkedNode<E> head = null;
private DLinkedNode<E> tail = null;
private int size;
// http://codereview.stackexchange.com/questions/63171/implementation-of-a-doubly-linked-list-in-java
public void addFirst(E item) {
DLinkedNode<E> newNode = new DLinkedNode<E>(item);
if (size < 1) {
newNode.next = null;
newNode.prev = null;
head = newNode;
tail = newNode;
} else {
head.prev = newNode;
newNode.next = head;
newNode.prev = null;
head = newNode;
}
size++;
}
private void addAfter(DLinkedNode<E> node, E item) {
//WHAT AM I DOING WRONG
DLinkedNode<E> newNode = new DLinkedNode<E>(item, node.next, node);
node.next = newNode;
//node.next.next = newNode; (maybe?)
if (node == tail) {
tail = newNode;
}
size++;
}
private E removeAfter(DLinkedNode<E> node) {
DLinkedNode<E> tempNext = node.next;
if (tempNext != null) {
node.next = tempNext.next;
node.next.prev = node;
size--;
return tempNext.data;
} else {
return null;
}
}
private E removeFirst() {
DLinkedNode<E> temp = head;
if (head != null) {
head = head.next;
head.prev = null;
}
if (temp != null) {
size--;
return temp.data;
} else {
return null;
}
}
public String toString() {
DLinkedNode<String> nodeRef = (DLinkedNode<String>) head;
StringBuilder result = new StringBuilder();
while (nodeRef != null) {
result.append(nodeRef.data);
if (nodeRef.next != null) {
result.append(" ==> ");
}
nodeRef = nodeRef.next;
}
return result.toString();
}
private DLinkedNode<E> getNode(int index) {
DLinkedNode<E> node = head;
for (int i = 0; i < index && node != null; i++) {
node = node.next;
}
return node;
}
public E get(int index) {
checkBounds(index);
DLinkedNode<E> node = getNode(index);
return node.data;
}
public E set(int index, E newValue) {
DLinkedNode<E> node = getNode(index);
E result = node.data;
node.data = newValue;
return result;
}
private void checkBounds(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(Integer.toString(index));
}
}
public void add(int index, E item) {
checkBounds(index);
if (index == 0) {
addFirst(item);
} else {
DLinkedNode<E> node = getNode(index - 1);
addAfter(node, item);
}
}
public boolean add(E item) {
add(size, item);
return true;
}
@Override
public E remove(int index) {
checkBounds(index);
if (index == 0) {
this.removeFirst();
} else {
DLinkedNode<E> myNode = getNode(index - 1);
return removeAfter(myNode);
}
return null;
}
@Override
public int size() {
return size;
}
public void printLinkedList() {
System.out.print(this.getClass().getSimpleName() + ": ");
DLinkedNode<E> myNode = head;
for (int i = 0; i < size && myNode != null; i++) {
if (i == size - 1) {
System.out.print(myNode.toString() + " [next: " + myNode.next
+ ", previous:" + myNode.prev + "] ");
} else {
System.out.print(myNode.toString() + " [next: " + myNode.next
+ ", previous:" + myNode.prev + "] " + ", ");
}
myNode = myNode.next;
}
}
}
Here is my main method:
public class MainTester {
public static void main(String[] args) {
DoubleLinkedList myList = new DoubleLinkedList();
double one = 1.0;
double two = 2.0;
double three = 3.0;
double four = 4.0;
double five = 5.0;
double six = 6.0;
myList.addFirst(one);
myList.add(two);
myList.add(three);
myList.add(four);
myList.add(five);
myList.add(six);
myList.printLinkedList();
System.out.println("\n\n");
myList.add(1,45.0);
myList.printLinkedList();
/*
System.out.println("\n\n");
myList.add(2, three);
myList.printLinkedList();
*/
}
}
Here is my output:
DoubleLinkedList: 1.0 [next: 2.0, previous:null] , 2.0 [next: 3.0, previous:1.0] , 3.0 [next: 4.0, previous:2.0] , 4.0 [next: 5.0, previous:3.0] , 5.0 [next: 6.0, previous:4.0] , 6.0 [next: null, previous:5.0]
DoubleLinkedList: 1.0 [next: 45.0, previous:null] , 45.0 [next: 2.0, previous:1.0] , 2.0 [next: 3.0, previous:1.0] , 3.0 [next: 4.0, previous:2.0] , 4.0 [next: 5.0, previous:3.0] , 5.0 [next: 6.0, previous:4.0] , 6.0 [next: null, previous:5.0]
Upvotes: 1
Views: 2096
Reputation: 897
DLinkedNode<E> newNode = new DLinkedNode<E>(item, node.next, node);
if (node.next != null)
node.next.prev = newNode;
newNode.next = node.next;
node.next = newNode;
newNode.prev = node;
This should get the desired order. Try drawing/visualizing - helps in ordering the statements.
Upvotes: 1