[数据结构与算法]数据结构之双向链表

双向链表

双向链表也叫双向表，是链表的一种，他由多个节点组成，每个结点都有一个数据域和两个指针域祖晨，数据域用来存储数据，其中一个指针域用来指向后继节点，两一个指针域用来指向前驱节点，链表的头结点的数据域不存储数据，指向前驱节点的指针域值为null，指向后继节点的指针域指向第一个真正存储数据的节点。

节点代码分析

class Node<T> {
    T item;
    Node next;
    Node pre;

    public Node(T item, Node next, Node pre) {
        this.item = item;
        this.next = next;
        this.pre = pre;
    }
}

代码实现

public class DoubleLinkList<T> implements Iterable<T> {

    private Node head;

    private Node last;

    private int N;


   private class Node {
        T item;
        Node next;
        Node pre;

        public Node(T item, Node next, Node pre) {
            this.item = item;
            this.next = next;
            this.pre = pre;
        }
    }

    public DoubleLinkList() {
       this.head = new Node(null,null,null);
       this.last = null;

       this.N = 0;
    }
    //清空链表
    public void clear(){
       this.head.next = null;
       this.last.next = null;
       this.head.item = 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;
    }

    //插入元素t
    public void insert(T t){
       if (isEmpty()) {
           Node node = new Node(t, null, head);
           last = node;
           head.next = last;
       }else {
           Node node1 = new Node(t, null, last);
           last.next = node1;
           last = node1;
       }

       N++;
    }

    //向指定位置i处插入元素t
    public void insert(int i,T t){
        Node n = head;
        for (int index = 0; index < i; i++ ) {
            n = n.next;
        }
        Node node = new Node(t, n.next, n);
        n.next = node;
        n.next.pre = node;
        N++;
    }

    //获取指定位置i处的元素
    public T get(int i){
        Node n = head.next;
        for (int index = 0; index < i; i++ ) {
            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;
    }

    //删除位置i处的元素，并返回该元素
    public T remove(int i){
        Node n = head;
        for (int index = 0; index < i; i++ ) {
            n = n.next;
        }
        Node node = n.next;
        n.next = n.next.next;
        n.next.pre = n;

        N--;
        return node.item;
    }

    @Override
    public Iterator<T> iterator() {
        return new TIterator();
    }

    private class TIterator implements Iterator{
        private Node n;
        public TIterator(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next;
            return n.item;
        }
    }



}