我已经多次发布了此代码，如果您继续关注此问题，我深表歉意。我已经为此工作了一段时间，所以到目前为止，任何帮助都会有所帮助，我已经尽我所能。但是当我的程序打印数据时，它会切换 8 和 7，我不知道为什么！这是所有代码。而且我还没有开始制作我的删除方法，所以忽略该功能。
public class MyLinkedList<AnyType> implements Iterable<AnyType> {
private int theSize;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
public class Node<AnyType> {
public Node(AnyType data, Node<AnyType> head, Node<AnyType> tail) {
myData = data;
myHead = head;
myTail = tail;
}
public AnyType myData;
public Node<AnyType> myHead;
public Node<AnyType> myTail;
}
public MyLinkedList() {
beginMarker = new Node(null, endMarker, null);
endMarker = new Node(null, null, beginMarker);
theSize = 0;
}
public void clear() {
beginMarker.myHead = endMarker;
endMarker.myTail = beginMarker;
}
public int size() {
return theSize;
}
public boolean exist(AnyType newVal) {
beginMarker.myHead.myData = newVal;
if (newVal != null) {
return true;
}
return false;
}
private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
Node<AnyType> new_node = new Node<>(newNode, previousNode.myTail, previousNode);
new_node.myTail.myHead = new_node;
previousNode.myTail = new_node;
theSize++;
}
public boolean add(AnyType newVal) {
{
add(size(), newVal);
return true;
}
}
public boolean add(int index, AnyType newVal) {
addBefore(getNode(index, 0, size()), newVal);
return true;
}
private Node<AnyType> getNode(int index) {
return getNode(index, 0, size() - 1);
}
public Node<AnyType> get(AnyType nodeData) {
Node<AnyType> node = beginMarker;
while (node != endMarker) {
// Means node.data = nodeData
if (node.myData.equals(nodeData)) {
return node;
}
}
return null;
}
// Added method
private Node<AnyType> getNode(int index, int lower, int upper) {
Node<AnyType> x;
if (index < lower || index > upper)
throw new IndexOutOfBoundsException();
if (index < size() / 2) {
x = beginMarker.myHead;
for (int i = 0; i < index; i++)
x = x.myHead;
} else {
x = endMarker.myTail;
for (int i = size(); i > index; i--) {
x = x.myTail;
}
}
return x;
}
public void printList() {
Node temp = beginMarker.myHead;
while (temp != null) {
System.out.println(temp.myData);
temp = temp.myHead;
}
}
public java.util.Iterator<AnyType> iterator() {
return new LinkedListIterator();
}
public void remove(AnyType removeVal) {
/*
* if(node.myData.equals(nodeData))
*
* MyLinkedList testList = new MyLinkedList();
*
* Node temp = testList.beginMarker.myData; while(temp != null){
*
* if(temp == removeVal){ temp.myTail = temp.myHead; temp.myHead =
* temp.myTail; } else{ temp.myHead = temp; }
*
*
* }
*/
}
private class LinkedListIterator implements java.util.Iterator<AnyType> {
private Node<AnyType> node_ = beginMarker;
public void remove() {
}
public boolean hasNext() {
if (node_.myHead != null) {
return true;
}
return false;
}
public AnyType next() {
if (!hasNext()) {
return null;
}
node_ = node_.myHead;
return node_.myData;
}
}
private static void testListIntegers() {
MyLinkedList<Integer> testList = new MyLinkedList<Integer>();
testList.add(new Integer(5));
testList.add(new Integer(4));
testList.add(new Integer(3));
System.out.println(" We have so far inserted " + testList.size() + " elements in the list");
testList.remove(4);
System.out.println(" Now, there is only " + testList.size() + " elements left in the list");
testList.add(1, new Integer(7));
testList.add(2, new Integer(8));
System.out.println(" About to print content of the list");
testList.printList();
}
private static void testListStrings() {
MyLinkedList<String> testList = new MyLinkedList<String>();
testList.add(new String("hello"));
testList.add(new String("this is"));
testList.add(new String("cs3345 project 2"));
System.out.println(" We have so far inserted " + testList.size() + " elements in the list");
testList.remove("this is");
System.out.println(" Now, there is only " + testList.size() + " elements left in the list");
testList.add(1, "a modified version of");
testList.add(2, "cs3345 project 2, call it version 2");
System.out.println(" About to print content of the list");
testList.printList();
}
public static void main(String args[]) throws Exception {
// Add whatever code you need here
// However, you will need to call both testListIntegers()
// and testListStrings()
testListIntegers();
testListStrings();
}
}
输出如下：
We have so far inserted 3 elements in the list
Now, there is only 3 elements left in the list
About to print content of the list
8
7
3
4
5
We have so far inserted 3 elements in the list
Now, there is only 3 elements left in the list
About to print content of the list
cs3345 project 2, call it version 2
a modified version of
cs3345 project 2
this is
hello
问题出在addBefore方法上：
private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
Node<AnyType> new_node = new Node<>(newNode, previousNode.myTail, previousNode);
new_node.myTail.myHead = new_node;
previousNode.myTail = new_node;
theSize++;
}
它就像：
private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
Node<AnyType> new_node = new Node<>(newNode, previousNode.myTail, previousNode);
previousNode.myHead = new_node;
previousNode.myTail = new_node;
theSize++;
}
所以基本上你正在打破双向链表。
编辑：
根据此处描述的算法，此方法应如下所示：
private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
Node<AnyType> new_node = new Node<>(newNode, previousNode, previousNode.myTail);
if(previousNode.myTail==null){
beginMarker.myHead = new_node;
} else {
previousNode.myTail.myHead = new_node;
}
previousNode.myTail = new_node;
theSize++;
}
看到您的列表是从 0 开始编制索引的，因此输出应该是：
5
7
8
4
3
下一个问题是printList方法（无限循环），因为某个地方错误地使用了开始/结束标记。
添加 theSize--; 在 remove 方法的末尾应该将元素从 3 减少到 1