双向链表如何维护prev指针
今天自己尝试实现了一下循环链表。然后按照自己的思路，出了一些小问题。
由于单链表是用head = head.next 来建立从前往后的链。是不是双链表要同时使用tail = tail.prev实现从后往前的链？
我自己的猜想是，按照我自己的思路写的代码，按照头插法建立的链表只是实现了从前往后的链接。而按照尾插法建立的链表只是实现了从后往前的链接，并没有实现真正意义上的双向链表。
以及还有add函数中出现的一个小问题：cur.prev空指针引用。我自己分析的原因是因为我没有维护过这个prev指针，但是如何维护它呢？
public void add(int index,E e) throws Exception {
if (index < 0 || index > size) throw new IndexOutOfBoundsException("add failed");
if(head == null) addFirst(e);
else if(index == getSize()) {
addLast(e);
}
else {
Node prevnode = getNode(index - 1);//getNode的作用：获取index位置的节点
Node nextnode = prevnode.next;//插入位置的节点
Node newNode = new Node(e, prevnode, nextnode);//待插入节点，前指针指向prevnode，后指针指向nextnode
prevnode.next = newNode;
nextnode.prev = newNode;
size ++;
/*
问题代码在这里：
Node cur = getNode(index);//获取index位置的元素
Node newnode = new Node(e , cur.prev ,cur);//用这样的方法测试出来cur.prev = null，该如何维护cur.prev？
cur.prev.next = newnode;
cur.prev = newnode;
size ++;
*/
}
}
完整代码如下：
package lineardatastructure;
public class DoubleLinkedList<E> {
private class Node{
E e;//当前节点的元素
Node next,prev;//下一个节点
public Node(E e,Node prev,Node next) {
this.e = e;
this.prev = prev;
this.next = next;
}
public Node(E e) {
this(e , null , null);
}
public Node() {}
@Override
public String toString() {
return e.toString();
}
}
public Node head,tail;
public int size;
public boolean isEmpty() {
return size == 0;
}
public int getSize() {
return size;
}
//获取index位置的元素
public E get(int index) throws Exception {
if(index > size || index < 0) throw new Exception("Get failed.");
if(index == 0 ) return head.e;
else{
Node cur = head;
for(int i = 0 ; i < index ; i ++) {
cur = cur.next;//找到当前节点
}
return cur.e;
}
}
//查找index位置的元素节点
public Node getNode(int index) throws Exception {
if(index > size || index < 0) throw new Exception("Get failed.");
if(index == 0 ) return head;
else if(index == this.getSize()) return tail;
else{
Node cur = head;
for(int i = 0 ; i < index ; i ++) {
cur = cur.next;
}
return cur;//找到当前节点
}
}
//头插法建立双链表
public void addFirst(E e) {
Node newnode = new Node(e,null,head);//新建一个节点，前一个节点指向空，后一个节点指向head
if(tail == null) {
tail = newnode;//如果尾结点为空，则尾结点指向当前插入元素
}
head = newnode;//头结点指向当前插入元素
size ++;
}
//尾插法建立双链表
public void addLast(E e) {
if(head == null) {//若链表为空，在链表中新建一个节点，让tail和head都指向这个节点
Node newnode = new Node(e , null , head);
tail = newnode;
head = newnode;
}
else {//链表不为空
Node newNode = new Node(e, tail, null);//新节点的prev指向原本的tail
tail.next = newNode;//tail.next指向newNode
tail = newNode;//把newNode作为新的tail
}
size++;
}
public void add(int index,E e) throws Exception {
if (index < 0 || index > size) throw new IndexOutOfBoundsException("add failed");
if(head == null) addFirst(e);
else if(index == getSize()) {
addLast(e);
}
else {
Node prevnode = getNode(index - 1);//getNode的作用：获取index位置的节点
Node nextnode = prevnode.next;//插入位置的节点
Node newNode = new Node(e, prevnode, nextnode);//待插入节点，前指针指向prevnode，后指针指向nextnode
prevnode.next = newNode;
nextnode.prev = newNode;
size ++;
/*
问题代码在这里：
Node cur = getNode(index);//获取index位置的元素
Node newnode = new Node(e , cur.prev ,cur);//用这样的方法测试出来cur.prev = null，该如何维护cur.prev？
cur.prev.next = newnode;
cur.prev = newnode;
size ++;
*/
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = head;
while(cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
正在回答
1回答
抱歉，我没有完整地看你的代码。简单的说一下双向链表添加节点的思路。
首先，和链表一样，需要找到带插入节点的前一个节点。那么相应的，也就知道了带插入节点的后一个节点。我管着两个节点叫做prevNode和nextNode。那么很显然，新节点的prev应该指向prevNode, 新节点的next应该指向nextNode。
之后和单链表一样，我们要把prevNode的next指向新的newNode，而不是以前的nextNode：
然后，核单链表不一样的，我们需要维护nextNode的prev，让它指向新的newNode，而不是以前的prevNode：
这样，就完成了新节点的插入，上面的图和下面的图是等价的：
当然，这里会有一些细节，比如插入第一个节点，preNode为空，要单独判断（如果没有dummyHead的话）；
再比如，插入最后一个节点，相当于nextNode为空，也要单独判断（相当于最后让nextNode的prev指向newNode没有了）。
请根据这个示意图，对照你的问题代码，仔细思考，你的问题代码，石佛士这个逻辑？如果不是，其实是什么逻辑？和这个逻辑的差异是什么？如果有需要，请单步跟踪，从一个空链表出发，添加三个节点。一步一步看，这三个节点添加的过程，逻辑在哪里，是怎么出现问题的？
进步就发生在这个过程中哦。
继续加油！：）
