雙向鏈表的節(jié)點(diǎn)比單鏈表的節(jié)點(diǎn)多一個(gè)pre域，也就是存放當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)地址的地方。

單鏈表里有許多操作是要找到待操作節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的，而雙向鏈表則不需要，因?yàn)殡p向鏈表可以得到當(dāng)前節(jié)點(diǎn)的前一個(gè)和后一個(gè)節(jié)點(diǎn)信息，可以完成相應(yīng)的操作。

雙向鏈表節(jié)點(diǎn)：

節(jié)點(diǎn)類：

class Node{
	//pre表示前一個(gè)節(jié)點(diǎn)，next表示后一個(gè)節(jié)點(diǎn)
	//no表示序號(hào)，其他為一些數(shù)據(jù)
	private Node pre;
	private Node next;
	private int no;
	private String name;
    private String nickname;
    public Node(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
	@Override
	public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
	//get set 方法省略
}

雙向鏈表類(帶頭節(jié)點(diǎn))：

雙向鏈表的基本操作后面追加

class TwoWayLinkedList{
	private Node head = new Node(0,"","");
	//無參構(gòu)造函數(shù)
	public TwoWayLinkedList(){
	}
	public void setHead(Node node){
		this.head = node;
	}
	public Node getHead(){
		return this.head;
	}
}

接下來就是給雙向鏈表類添加一些基本方法了，插入這里提供按序號(hào)插入法，其他插入類似，然后就是刪除，修改，遍歷方法了。

添加節(jié)點(diǎn)方法(按序號(hào)插入)，該方法在雙向鏈表類內(nèi)部

思路：

插入節(jié)點(diǎn)的插入位置在cur指針的前面時(shí)

1.插入時(shí)先設(shè)置待插入節(jié)點(diǎn)的node的pre域，即把cur的pre域設(shè)置為node的pre域

2.再把cur的pre域?qū)?yīng)節(jié)點(diǎn)的next域設(shè)為node

3.然后將cur的的pre域設(shè)為node，node的next域設(shè)為cur 即：

node.setPre(cur.getPre());

node.setNext(cur);

cur.getPre().setNext(node);

cur.setPre(node);

插入節(jié)點(diǎn)的插入位置在cur指針后面時(shí)又分為：在鏈表尾部插入和在鏈表頭部插入(即鏈表為空時(shí)插入第一個(gè)節(jié)點(diǎn))

特別注意：插入第一個(gè)節(jié)點(diǎn)時(shí)和在鏈表尾部插入時(shí)，cur很容易出現(xiàn)空指針異常，所以要分三種插入的情況

參數(shù)：節(jié)點(diǎn)(Node)

返回值：無

public void add(Node node){
	//先判斷鏈表是否為空，為空說明這是插入的第一個(gè)節(jié)點(diǎn)
	//第一個(gè)節(jié)點(diǎn)插入因?yàn)閔ead的next域?yàn)榭?
	//head.getNext().getPre()會(huì)報(bào)空指針異常錯(cuò)誤
	//所以給第一個(gè)節(jié)點(diǎn)設(shè)置pre域時(shí)要直接指向head
	if(head.getNext()==null){
		node.setNext(head.getNext());
		node.setPre(head);
		head.setNext(node);
		return;
	}
	//代碼走到這里說明雙向鏈表至少有一個(gè)節(jié)點(diǎn)
	//創(chuàng)建一個(gè)cur指針，指向鏈表的第一個(gè)節(jié)點(diǎn)
	Node cur = head.getNext();
	//如果cur指向最后一個(gè)節(jié)點(diǎn)還沒有比待插入節(jié)點(diǎn)序號(hào)大的
	//就插入到鏈表最后
	while(true){
		//如果cur當(dāng)前指向的節(jié)點(diǎn)序號(hào)大于待插入節(jié)點(diǎn)的序號(hào)
		//說明待插入節(jié)點(diǎn)應(yīng)該插在cur當(dāng)前指向節(jié)點(diǎn)的前一個(gè)位置
		//插入之后就退出循環(huán)，插入方法也就執(zhí)行完了
		if(cur.getNo()>node.getNo()){
			node.setPre(cur.getPre());
			node.setNext(cur);
			cur.getPre().setNext(node);
			cur.setPre(node);
			break;
		}else if(cur.getNo()==node.getNo()){
			//編號(hào)存在就不插入，退出循環(huán)
			System.out.printf("編號(hào)%d已存在\n",node.getNo());
			break;
		}else if(cur.getNext()==null){
			//判斷當(dāng)前cur指向的是不是最后一個(gè)節(jié)點(diǎn)
			//如果是，就插入到鏈表最后
			//進(jìn)入這個(gè)if分支
			//說明待插入節(jié)點(diǎn)序號(hào)比前面節(jié)點(diǎn)序號(hào)都大
			//而且待插入節(jié)點(diǎn)序號(hào)不存在于鏈表中
			node.setPre(cur);
			cur.setNext(node);
			//節(jié)點(diǎn)初始化時(shí)，其pre與next默認(rèn)指向null
			//所以不需要讓node的next域再設(shè)置為null
			//或者設(shè)為cur的next域
			break;
		}
		//如果上面的if分支一個(gè)都沒進(jìn)入
		//說明cur指向的節(jié)點(diǎn)不滿足，讓cur指向下一個(gè)節(jié)點(diǎn)
		cur = cur.getNext();
	}
}

插入方法寫好之后就可以寫遍歷方法，將雙向鏈表進(jìn)行打印輸出，該方法還是在雙向鏈表類內(nèi)部

參數(shù)：無

返回值：無

public void print(){
	//先判斷鏈表是否為空
	if(head.getNext()==null){
		System.out.println("雙向鏈表為空");
		return;
	}
	//定義一個(gè)cur指針指向鏈表的頭節(jié)點(diǎn)，然后遍歷鏈表
	Node cur = head;
	//開始遍歷
	while(true){
		//cur指向鏈表最后一個(gè)節(jié)點(diǎn)就退出循環(huán)
		if(cur.getNext()==null){
			break;
		}
		//因?yàn)閏ur初始化是head
		//所以打印cur指向的下一個(gè)節(jié)點(diǎn)
		//打印時(shí)需要打印當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)
		//避免插入時(shí)節(jié)點(diǎn)pre域出現(xiàn)問題
		System.out.println("now:"+cur.getNext()+
		"pre:"+cur.getNext().getPre());
		//然后讓cur指向下一個(gè)節(jié)點(diǎn)
		cur = cur.getNext();
	}
}

鏈表刪除思路：

1.先遍歷通過cur找到待刪除節(jié)點(diǎn)

此時(shí)cur指向的就是待刪除節(jié)點(diǎn)，讓待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next域直接跨過待刪除節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的next域。

2.讓待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的pre域直接跨過待刪除節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的pre域

cur.getPre().setNext(cur.getNext());

cur.getNext().setPre(cur.getPre());

特別注意：如果待刪除節(jié)點(diǎn)是鏈表最后一個(gè)，那么cur.getNext()就為空，2)的操作就會(huì)出現(xiàn)空指針異常，這里需要判斷一下

參數(shù)：待刪除節(jié)點(diǎn)的序號(hào)(int)

返回值：無

該方法仍然在雙向鏈表內(nèi)部

public void remove(int no){
	//先判斷鏈表是否為空
	if(head.getNext()==null){
		System.out.println("鏈表為空");
		return;
	}
	//創(chuàng)建一個(gè)cur指針來遍歷鏈表，初始化指向鏈表第一個(gè)節(jié)點(diǎn)
	Node cur = head.getNext();
	while(true){
		if(cur.getNo()==no){//找到待刪除節(jié)點(diǎn)
			cur.getPre().setNext(cur.getNext());
			if(cur.getNext()!=null){
				//如果待刪除節(jié)點(diǎn)為鏈表最后一個(gè)節(jié)點(diǎn)
				//不執(zhí)行下面語句
				cur.getNext().setPre(cur.getPre());
			}
			break;
		}else if(cur.getNext()==null){
			//當(dāng)前cur指向的是鏈表最后一個(gè)節(jié)點(diǎn)
			//說明沒有傳來的序號(hào)匹配不到待刪除節(jié)點(diǎn)
			System.out.println("沒有該編號(hào):"+no+"節(jié)點(diǎn)");
			break;
		}
		//未執(zhí)行上面代碼，讓cur后移
		cur = cur.getNext();
	}
}

鏈表修改節(jié)點(diǎn)信息思路：

修改節(jié)點(diǎn)信息與刪除節(jié)點(diǎn)類似，遍歷找到待更新節(jié)點(diǎn)，然后替換信息，未找到就在控制臺(tái)輸出提醒，不可修改節(jié)點(diǎn)序號(hào)

參數(shù)：一個(gè)節(jié)點(diǎn)(node)

返回值：無

public void update(Node node){
	//先判斷鏈表是否為空
	if(head.getNext()==null){
		System.out.println("鏈表為空");
		return;
	}
	//創(chuàng)建一個(gè)cur指針來遍歷鏈表，初始化指向鏈表第一個(gè)節(jié)點(diǎn)
	Node cur = head.getNext();
	while(true){
		if(cur.getNo()==node.getNo()){//找到待修改節(jié)點(diǎn)
			//修改節(jié)點(diǎn)信息
			cur.setName(node.getName());
			cur.setNickname(node.getNickname());
			break;
		}else if(cur.getNext()==null){
			//當(dāng)前cur指向的是鏈表最后一個(gè)節(jié)點(diǎn)
			//說明傳來節(jié)點(diǎn)的序號(hào)匹配不到
			System.out.println("沒有該編號(hào):"
			+node.getNo()+"節(jié)點(diǎn)");
			break;
		}
		//未執(zhí)行上面代碼，讓cur后移
		cur = cur.getNext();
	}
}

之前單鏈表的操作，如：單鏈表長度，獲取倒數(shù)第k個(gè)節(jié)點(diǎn)，單鏈表反轉(zhuǎn)，單鏈表反向輸出，合并兩個(gè)有序單鏈表為一個(gè)單鏈表且仍然有序。

雙向鏈表的操作，下面直接給出代碼，思路是和單鏈表的類似，就是設(shè)置節(jié)點(diǎn)pre域麻煩一點(diǎn)。

雙向鏈表全部代碼如下：

package com.sixteen.linkedlist;
public class TwoWayLinkedListDemo {
    public static void main(String[] args) {
        TwoWayLinkedList twoWayLinkedList = new TwoWayLinkedList();
        twoWayLinkedList.add(new Node(1,"宋江","及時(shí)雨"));
        twoWayLinkedList.add(new Node(3,"吳用","智多星"));
        twoWayLinkedList.add(new Node(2,"盧俊義","玉麒麟"));
        twoWayLinkedList.add(new Node(4,"林沖","豹子頭"));
        System.out.println("原雙向鏈表-----");
        twoWayLinkedList.print();
        /*System.out.println(getSize(twoWayLinkedList.getHead()));
        twoWayLinkedList.update(new Node(2,"盧俊義222","玉麒麟222"));
        System.out.println("修改后的雙向鏈表-----");
        twoWayLinkedList.print();*/
        /*System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 1));
        System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 4));
        System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 2));
        System.out.println(getTheLastIndexNode(twoWayLinkedList.getHead(), 6));*/
        /*twoWayLinkedList.remove(3);
        System.out.println("-----");
        twoWayLinkedList.print();*/
        /*//reversePrint(twoWayLinkedList.getHead());
        reverse(twoWayLinkedList.getHead());
        System.out.println("反轉(zhuǎn)后的雙向鏈表-----");
        twoWayLinkedList.print();*/
        /*TwoWayLinkedList twoWayLinkedList1 = new TwoWayLinkedList();
        twoWayLinkedList1.add(new Node(1,"宋江","及時(shí)雨"));
        twoWayLinkedList1.add(new Node(3,"吳用","智多星"));
        twoWayLinkedList1.add(new Node(5,"盧俊義","玉麒麟"));
        twoWayLinkedList1.add(new Node(7,"林沖","豹子頭"));
        TwoWayLinkedList twoWayLinkedList2 = new TwoWayLinkedList();
        twoWayLinkedList2.add(new Node(2,"宋江2","及時(shí)雨2"));
        twoWayLinkedList2.add(new Node(4,"吳用4","智多星4"));
        twoWayLinkedList2.add(new Node(6,"盧俊義6","玉麒麟6"));
        twoWayLinkedList2.add(new Node(8,"林沖8","豹子頭8"));
        TwoWayLinkedList twoWayLinkedList = mergeTwoTwoWayLinkedList(twoWayLinkedList1, twoWayLinkedList2);
        twoWayLinkedList.print();*/
    }
    public static Node getTheLastIndexNode(Node head,int index){
        if (head.getNext()==null){
            return null;
        }
        int size = getSize(head);
        if (index<0 || index>size){
            return null;
        }
        Node temp = head.getNext();
        for (int i = 0; i < size-index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }
    public static int getSize(Node head){
        if (head.getNext()==null){
            return 0;
        }
        int count = 0;
        Node temp = head.getNext();
        while (temp!=null){
            count++;
            temp = temp.getNext();
        }
        return count;
    }
    public static TwoWayLinkedList mergeTwoTwoWayLinkedList(TwoWayLinkedList twoWayLinkedList1,                                                            TwoWayLinkedList twoWayLinkedList2){
        Node head1 = twoWayLinkedList1.getHead();
        Node head2 = twoWayLinkedList2.getHead();
        if (head1.getNext()==null || head2.getNext()==null){
            return head1.getNext()==null ? twoWayLinkedList2:twoWayLinkedList1;
        }
        Node cur = head1.getNext();
        Node node;
        while (cur!=null){
            node = cur;
            cur = cur.getNext();
            twoWayLinkedList2.add(node);
        }
        return twoWayLinkedList2;
    }
    public static void reverse(Node head){
        //如果鏈表為空或鏈表只有一個(gè)元素，不做任何操作
        if (head.getNext()==null){
            System.out.println("鏈表為空");
            return;
        }
        if (head.getNext().getNext()==null){
            return;
        }
        Node temp = head.getNext();
        Node reverseNode = new Node(0,"","");
        Node node;
        while (temp!=null){
            node = temp;
            temp = temp.getNext();
            if (reverseNode.getNext()==null){
                node.setNext(reverseNode.getNext());
                node.setPre(reverseNode);
                reverseNode.setNext(node);
            }else {
                node.setNext(reverseNode.getNext());
                node.setPre(reverseNode);
                reverseNode.getNext().setPre(node);
                reverseNode.setNext(node);
            }
        }
        head.setNext(reverseNode.getNext());
    }
    public static void reversePrint(Node head){
        //鏈表為空或者鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，直接輸出
        if (head.getNext()==null){
            System.out.println("鏈表為空");
            return;
        }
        if (head.getNext().getNext()==null){
            System.out.println(head.getNext());
            return;
        }
        Node temp = head.getNext();
        //while循環(huán)結(jié)束之后temp定位到最后一個(gè)節(jié)點(diǎn)，然后再反向遍歷鏈表
        while (temp.getNext()!=null){
            temp = temp.getNext();
        }
        while (temp.getPre()!=null){
            System.out.println(temp);
            temp = temp.getPre();
        }
    }
}
class TwoWayLinkedList{
    private Node head = new Node(0,"","");
    public Node getHead() {
        return head;
    }
    public void setHead(Node head) {
        this.head = head;
    }
    public void add(Node node){
        if (head.getNext()==null){
            node.setPre(head);
            node.setNext(head.getNext());
            head.setNext(node);
            return;
        }
        Node cur = head.getNext();
        while (true){
            if (cur.getNo()>node.getNo()){
                node.setPre(cur.getPre());
                node.setNext(cur);
                cur.getPre().setNext(node);
                cur.setPre(node);
                break;
            }else if (cur.getNo()==node.getNo()){
                System.out.printf("編號(hào)%d已存在\n",node.getNo());
                break;
            }else if (cur.getNext()==null){
                node.setPre(cur);
                cur.setNext(node);
                break;
            }
            cur = cur.getNext();
        }
    }
    public void remove(int no){
        if (head.getNext()==null){
            System.out.println("鏈表為空");
            return;
        }
        Node cur = head.getNext();
        while (true){
            if (cur.getNo()==no){
                cur.getPre().setNext(cur.getNext());
                if (cur.getNext()!=null){//如果當(dāng)前cur指向的是鏈表最后一個(gè)節(jié)點(diǎn)，就不執(zhí)行下面的操作
                    cur.getNext().setPre(cur.getPre());
                }
                if (cur.getNext()==null){//找到相應(yīng)節(jié)點(diǎn)且這個(gè)節(jié)點(diǎn)是最后一個(gè)節(jié)點(diǎn)
                    cur.getPre().setNext(null);
                }else {
                    cur.getPre().setNext(cur.getNext());
                    cur.getNext().setPre(cur.getPre());
                }
                break;
            }else if (cur.getNext()==null){
                System.out.println("沒有編號(hào)"+no+"的節(jié)點(diǎn)");
                break;
            }
            cur = cur.getNext();
        }
    }
    public void update(Node node){
        if (head.getNext()==null){
            System.out.println("鏈表為空");
            return;
        }
        Node cur = head.getNext();
        while (true){
            if (cur.getNo()==node.getNo()){
                cur.setName(node.getName());
                cur.setNickname(node.getNickname());
                break;
            }else if (cur.getNext()==null){
                System.out.println("沒有編號(hào)"+node.getNo()+"節(jié)點(diǎn)");
                break;
            }
            cur = cur.getNext();
        }
    }
    public void print(){
        if (head.getNext()==null){
            System.out.println("鏈表為空");
            return;
        }
        Node cur = head;
        while (true){
            if (cur.getNext()==null){
                break;
            }
            System.out.println("now:"+cur.getNext()+
                    "pre:"+cur.getNext().getPre());
            cur = cur.getNext();
        }
    }
}
class Node{
    private Node pre;
    private Node next;
    private int no;
    private String name;
    private String nickname;
    public Node(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
    public Node getPre() {
        return pre;
    }
    public void setPre(Node pre) {
        this.pre = pre;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getNickname() {
        return nickname;
    }
    public void setNickname(String nickname) {
        this.nickname = nickname;
    }
}