线性表
双向链表
定义
双向链表（双链表），多个结点，每个节点=一个数据域+两个指针域，数据域存数据，指针域分前后，前一个指针域指向前驱结点，后一个指针域指向后继结点。头结点数据域不存储数据，头结点指向前驱结点的指针域的值为null，指向后继结点的指针域指向第一个真正存储数据的结点；尾结点指向后继结点的指针域为null。
图示
代码实现
按照面向对象的思想，设计一个类，描述结点，结点属于链表，所有把结点类作为链表类的内部类来实现
链表类
public class DoublyLinkedList<T> implements Iterable<T>{//头结点private Node head;//尾结点private Node last;//链表长度（元素实际个数，头结点不算）private int N;//--------------------------------------------------//结点类private class Node{//存储数据public T item;//指向上一个结点public Node pre;//指向下一个结点public Node next;//结点类的构造器public Node( Node pre,T item, Node next) {this.pre = pre;this.item = item;this.next = next;}}//--------------------------------------------------//构造器public DoublyLinkedList(){//初始化头结点和尾结点this.head = new Node(null,null,null);this.last = null;//初始化元素个数this.N = 0;}//--------------------------------------------------//清空链表public void clear(){this.head.pre = null;this.head.item = null;this.head.next = null;this.last = null;this.N = 0;}//--------------------------------------------------//返回链表长度public int length(){return N;}//--------------------------------------------------//判断链表是否为空public boolean isEmpty(){return N == 0;}//--------------------------------------------------//获取第一个元素(不是第一个结点，第一个结点不存数据）public T getFirst(){if(isEmpty()){return null;}return head.next.item;}//--------------------------------------------------//获取最后一个元素public T getLast(){if(isEmpty()){return null;}return last.item;}//--------------------------------------------------//添加元素public void add(T t){if(isEmpty()){//为空//创建新结点,指向前驱结点，也就是头结点Node newNode = new Node(head, t,null);//让新结点成为尾结点last = newNode;//让头结点指向尾结点head.next = last;}else{//链表非空//创建一个oldLast结点代替last，避免冲突Node oldLast = last;//创建新结点，指向了当前尾结点Node newNode = new Node(oldLast, t, null);//让当前尾结点指向新结点last.next = newNode;//让新结点成为尾结点last = newNode;}N++;}//--------------------------------------------------//向指定位置插入元素public void insert(int i, T t){//找到i位置的前一个结点Node preNode = head;for(int index = 0; index<i; index++){preNode = preNode.next;}//找到i位置的结点Node currNode = preNode.next;//创建新结点Node newNode = new Node(preNode,t,currNode);//让原i位置的原前一个结点的指向新结点preNode.next = newNode;//让i位置的结点指向新结点currNode.pre = newNode;//元素个数加1N++;}//--------------------------------------------------//获取指定位置处的元素public T get(int i){Node n = head.next;for(int index = 0; index<i; index++){n = n.next;}return n.item;}//--------------------------------------------------//找到元素t在链表中第一次出现的位置public int indexOf(T t){Node n = head;for(int i = 0; n.next != null; i++){n = n.next;if(n.item.equals(t)){return i;}}return -1;}//--------------------------------------------------//删除指定位置处的元素，并返回该元素public T remove(int i){//找到i位置的前一个结点Node pre = head;for(int index = 0; index<i; index++){pre = pre.next;}//找到i位置的结点Node currNode = pre.next;//找到i位置的下一个结点Node nextNode = currNode.next;//让i位置的前一个节点指向i位置的下一个结点pre.next = nextNode;//让i位置的下一个结点指向i位置的前一个节点nextNode.pre = pre;//元素个数减1N--;return currNode.item;}//--------------------------------------------------@Overridepublic Iterator iterator() {return new DIterator();}//--------------------------------------------------//定义内部类实现iterator接口，重写next和hasNext方法private class DIterator implements Iterator{private Node n;public DIterator(){this.n = head;}@Overridepublic boolean hasNext() {return n.next != null;}@Overridepublic Object next() {n = n.next;return n.item;}}}
测试类
public class DoublyLinkedListTest {public static void main(String[] args) {DoublyLinkedList dll = new DoublyLinkedList();dll.add("姚明");dll.add("科比");dll.add("乔丹");//测试迭代遍历System.out.println("----------------测试遍历--------------------");for(String obj : dll){System.out.println(obj);}System.out.println("----------------测试插入--------------------");dll.insert(1,"杜兰特");dll.insert(2,"奥尼尔");for(String obj : dll){System.out.println(obj);}System.out.println("---------获取第一个和最后一个结点的值------------");System.out.println(dll.getFirst());;System.out.println(dll.getLast());System.out.println("---------获取指定元素第一次出现的位置-------------");System.out.println(dll.indexOf("科比"));System.out.println("--------------测试删除----------------------");System.out.println(dll.remove(2));System.out.println("--------------清空链表----------------------");dll.clear();for(String obj : dll){System.out.println(obj);}}}
结果
----------------测试遍历--------------------
姚明
科比
乔丹
----------------测试插入--------------------
姚明
杜兰特
奥尼尔
科比
乔丹
---------获取第一个和最后一个结点的值------------
姚明
乔丹
---------获取指定元素第一次出现的位置-------------
3
--------------测试删除----------------------
奥尼尔
--------------清空链表----------------------
