[数据结构与算法]双向循环链表(线性表 栈 队列)

我们在上期学习了链表的概念与结构。了解到单向链表和单向循环链表，我们在这里继续扩展一下，有单向则就就有双向。所以我们这期学习双向循环链表。乃什么是什么循环链表呢？

概念

双向循环链表: 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

与单向循环链表不同的是每个节点都有自己的直接前驱。

图示

此处我们使用LinkedList类来实现双向循环链表

我们用这个双向循环链表可以实现我们的线性表，栈以及队列。就是实现各个接口就可以。让我们以及去分析一下这个LinkedList吧.

解析

对于链表肯定有节点。所以我肯定得先定义一个节点类。定义有它的类似数据域的值，直接前驱，直接后继。然后在去定义三个构造方法。一个是无参构造。一个是传数据的构造函数，一个是传数据，直接前驱，直接后继三个参数的构造函数，以及数据的toString()方法。我们把这个节点类写完就可以定义自己的头指针，尾指针和有效元素个数。再定义构造函数。再去定义

代码实现

    private class Node {
        E data;
        Node pre;   //直接前驱
        Node next;  //直接后继

        public Node() {
            this(null, null, null);
        }

        public Node(E data) {
            this(data, null, null);
        }

        public Node(E data, Node pre, Node next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    private Node head;
    private Node tail;
    private int size;

    public LinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

上面属性定义完后就是实现我们所有接口的方法。我们先实现线性表List接口的方法。

首先是添加方法add();我们默认就直接在表尾添加。若如果是在指定索引处添加的话，首先肯定是判断传入索引的值是否合格。添加元素肯定是添加的是节点，所以我们先创建一个节点。再就是判断有效元素为0的话，则就是把头指针指向该节点，尾指针也指向该节点尾指针的下一跳指向头节点，头节点的前驱指向尾节点。如果是在头节点处添加元素，则让该节点的前驱指向指向头节点的前驱该节点的下一跳指向头节点，让头节点的前驱指向该节点，再让头指针指向该节点，最后让尾指针的下一跳指向头节点。如果是在表尾添加元素，则是让该节点的下一跳指向尾节点的下一跳，尾指针的下一跳指向该节点，让该节点的前驱指向尾节点，尾指针在指向该节点，然后让头节点的前驱指向尾节点。其实在表头和表尾添加元素的操作刚好是对称的。如果是在中间添加元素的话，我们是需要遍历的。但由于是双向的，所以我们得考虑是从左开始遍历还是从右开始遍历，就拿有效元素的个数除2进行判断。老样子，创建节点，但这里是创建两个。让p节点先指向头节点，遍历到要添加位置的前一个结点，该结点的后继结点则是要添加位置的后一个结点q。让p的后继指向添加结点，让添加结点的前指向p，让q的前驱前驱结点指向添加结点。最后让添加结点的后继指向q。如果从尾结点开始遍历的话，就p从指向尾节点开始，开始遍历，是往左开始遍历的。其大致思想与从左边开始遍历是一样的。只要添加元素我们的有效元素个数就要进行加一。

图示

代码实现

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index out of range");
        }
        Node n = new Node(element);
        if (size == 0) {
            head = n;
            tail = n;
            tail.next = head;
            head.pre = tail;
        } else if (index == 0) {
            n.pre = head.pre;
            n.next = head;
            head.pre = n;
            head = n;
            tail.next = head;
        } else if (index == size) {
            n.next = tail.next;
            tail.next = n;
            n.pre = tail;
            tail = n;
            head.pre = tail;
        } else {
            Node p, q;
            if (index <= size / 2) {
                p = head;
                for (int i = 0; i < index - 1; i++) {
                    p = p.next;
                }
                q = p.next;
                p.next = n;
                n.pre = p;
                q.pre = n;
                n.next = q;
            } else {
                p = tail;
                for (int i = size - 1; i > index; i--) {
                    p = p.pre;
                }
                q = p.pre;
                q.next = n;
                n.pre = q;
                n.next = p;
                p.pre = n;
            }
        }
        size++;
    }

添加方法写完后，乃接下来就是删除方法了。

删除元素肯定先要判断是否包含该元素，我们调用后面的方法是否能得出索引值，要是返回的不是-1，则就能找到要删除的元素。

删除指定索引处的元素方法首先也是判断索引值是否满足条件。先创建一个结点，如果是只有一个元素，那就是删除此元素。就让头指针指向null,让尾指针指向null;如果是在表头删除，该结点指向头节点的后继，然后在让头结点的后继指向null，再让该节点的前驱指向头节点的前驱，再把头节点的头节点的前驱指向null，这样就把头结点隔离出，再让头指针指向该节点，最后让尾指针的下一跳指向该节点。如果在表的末尾删除，创建的这个结点就是尾结点的前驱，在把尾节点的前驱指向null，把尾节点的下一跳地址给该结点的下一跳，再让尾结点的下一跳指向null,让尾结点指向该节点，最后让头结点的前驱指向该节点。如果是在中间进行删除的话。我们得创建三个结点。也是同理判断从那边开始遍历。如果从左边开始遍历，让p结点遍历到要删除结点的前驱，而p结点的后继下一跳就是q结点，也就是要删除的元素。乃r结点的后继则是r结点。让p结点的下一跳指向r结点r结点的前驱指向p，让q结点的下一跳指向null,让q的前驱指null；如果从右边开始遍历，其实都是一样的道理。乃我们删除元素肯定要记得有效元素个数减一。

?

?

代码如下

 @Override
    public void remove(E element) {
        int index = indexOf(element);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove index out of range");
        }
        E ret = null;
        Node node;
        if (size == 1) {
            ret = head.data;
            head = null;
            tail = null;
        } else if (index == 0) {
            ret = head.data;
            node = head.next;
            head.next = null;
            node.pre = head.pre;
            head.pre = null;
            head = node;
            tail.next = head;
        } else if (index == size - 1) {
            ret = tail.data;
            node = tail.pre;
            tail.pre = null;
            node.next = tail.next;
            tail.next = null;
            tail = node;
            head.pre = tail;
        } else {
            Node p, q, r;
            if (index <= size / 2) {
                p = head;
                for (int i = 0; i < index - 1; i++) {
                    p = p.next;
                }
                q = p.next;
                r = q.next;
                ret = q.data;
                p.next = r;
                r.pre = p;
                q.next = null;
                q.pre = null;
            } else {
                p = tail;
                for (int i = size - 1; i > index + 1; i--) {
                    p = p.pre;
                }
                q = p.pre;
                r = q.pre;
                ret = q.data;
                r.next = p;
                p.pre = r;
                q.next = null;
                q.pre = null;
            }
        }
        size--;
        return ret;
    }

获取某索引处的元素就是get(element)方法；老规矩是先判断索引值。如果是表头则就直接返回头节点的数据。尾节点处也是同样的。若是获取中间的数据，则就是遍历到该索引处的结点，则直接返回该结点的数据域；

set()方法和get()方法其实是一样，只是通过找具体索引的结点，把新元素赋给该结点的数据域即可。

代码如下

 @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get index out of range");
        }
        if (index == 0) {
            return head.data;
        } else if (index == size - 1) {
            return tail.data;
        } else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            return p.data;
        }
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("set index out of range");
        }
        E ret = null;
        if (index == 0) {
            ret = head.data;
            head.data = element;
        } else if (index == size - 1) {
            ret = tail.data;
            tail.data = element;
        } else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            ret = p.data;
            p.data = element;
        }
        return ret;
    }

返回有效元素个数就直接返回size的大小即可；找具体元素的索引值，这里也是从头结点开始遍历。定义index为0；用while循环操作，如果每此遍历的结点的数据域元素与需要查找的元素不相同就一直进行遍历；遍历一次index加一，如果遍历到头结点了，则就然会-1；最终结果返回index的值即可。contains()方法判断是否包含传入的元素。直接返回indexOf()函数是否不等于1，如果不是-1则就是包含。判空也就是那size是否为0并且头节点和尾节点是否指向空。清空函数就直接让头指针指向null，尾指针指向null，size等于0即可。

代码如下

   @Override
    public int size() {
        return size;
    }
    @Override
    public int indexOf(E element) {
        Node p = head;
        int index = 0;
        while (!p.data.equals(element)) {
            p = p.next;
            index++;
            if (p == head) {
        return -1;
    }
}
        return index;
                }
    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }
    @Override
    public boolean isEmpty() {
        return size == 0 && head == null && tail == null;
    }

    @Override
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

我们再来讲一下排序操作。我们使用插入排序来做。如果为空或者只有一个元素即直接结束。

定义一个节点A，让A指向头节点的下一跳。判断条件肯定是A遍历完肯定不再回到head；

取A数据域的值暂存起来。在创建两个结点B和C，让B指向A，C是B的前驱，判断条件是如果C不指向尾指针并且C中的数据域值大于暂存的值；如果满足则让C数据域的值赋给B数据域。最后再让

暂存的值赋给B的数据域的值。

代码如下

  @Override
    public void sort(Comparator<E> c) {
        if (c == null) {
            throw new IllegalArgumentException("comparator can not be null");
        }
        //插入排序来做
        if (size == 0 || size == 1) {
            return;
        }
        for (Node nodeA = head.next; nodeA != head; nodeA = nodeA.next) {
            E e = nodeA.data;
            Node nodeB;
            Node nodeC;
            for (nodeB = nodeA, nodeC = nodeB.pre; nodeC != tail && c.compare(nodeC.data, e) > 0; nodeB = nodeB.pre, nodeC = nodeC.pre) {
                nodeB.data = nodeC.data;
            }
            nodeB.data = e;
        }
    }

截取子链表函数，toStrig()以及迭代器方法和单向循环链表是一样的。所以我们就不在这分析了。

对于栈和队列的一些方法我们就通过我们刚写过的方法内部直接调用即可。乃我们就直接上完整代码吧。

完整代码

package P3.链式结构;

import p1.接口.Dequeue;
import p1.接口.List;
import p1.接口.Stack;

import java.util.Comparator;
import java.util.Iterator;

//双向循环链表
public class LinkedList<E> implements List<E>, Dequeue<E>, Stack<E>{

    private class Node {
        E data;
        Node pre;   //直接前驱
        Node next;  //直接后继

        public Node() {
            this(null, null, null);
        }

        public Node(E data) {
            this(data, null, null);
        }

        public Node(E data, Node pre, Node next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    private Node head;
    private Node tail;
    private int size;

    public LinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    public LinkedList(E[] arr) {
        if (arr == null) {
            throw new IllegalArgumentException("arr can not be null");
        }
        for (E e : arr) {
            add(e);
        }
    }

    @Override
    public void add(E element) {
        add(size, element);
    }

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index out of range");
        }
        Node n = new Node(element);
        if (size == 0) {
            head = n;
            tail = n;
            tail.next = head;
            head.pre = tail;
        } else if (index == 0) {
            n.pre = head.pre;
            n.next = head;
            head.pre = n;
            head = n;
            tail.next = head;
        } else if (index == size) {
            n.next = tail.next;
            tail.next = n;
            n.pre = tail;
            tail = n;
            head.pre = tail;
        } else {
            Node p, q;
            if (index <= size / 2) {
                p = head;
                for (int i = 0; i < index - 1; i++) {
                    p = p.next;
                }
                q = p.next;
                p.next = n;
                n.pre = p;
                q.pre = n;
                n.next = q;
            } else {
                p = tail;
                for (int i = size - 1; i > index; i--) {
                    p = p.pre;
                }
                q = p.pre;
                q.next = n;
                n.pre = q;
                n.next = p;
                p.pre = n;
            }
        }
        size++;
    }

    @Override
    public void remove(E element) {
        int index = indexOf(element);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove index out of range");
        }
        E ret = null;
        Node node;
        if (size == 1) {
            ret = head.data;
            head = null;
            tail = null;
        } else if (index == 0) {
            ret = head.data;
            node = head.next;
            head.next = null;
            node.pre = head.pre;
            head.pre = null;
            head = node;
            tail.next = head;
        } else if (index == size - 1) {
            ret = tail.data;
            node = tail.pre;
            tail.pre = null;
            node.next = tail.next;
            tail.next = null;
            tail = node;
            head.pre = tail;
        } else {
            Node p, q, r;
            if (index <= size / 2) {
                p = head;
                for (int i = 0; i < index - 1; i++) {
                    p = p.next;
                }
                q = p.next;
                r = q.next;
                ret = q.data;
                p.next = r;
                r.pre = p;
                q.next = null;
                q.pre = null;
            } else {
                p = tail;
                for (int i = size - 1; i > index + 1; i--) {
                    p = p.pre;
                }
                q = p.pre;
                r = q.pre;
                ret = q.data;
                r.next = p;
                p.pre = r;
                q.next = null;
                q.pre = null;
            }
        }
        size--;
        return ret;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get index out of range");
        }
        if (index == 0) {
            return head.data;
        } else if (index == size - 1) {
            return tail.data;
        } else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            return p.data;
        }
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("set index out of range");
        }
        E ret = null;
        if (index == 0) {
            ret = head.data;
            head.data = element;
        } else if (index == size - 1) {
            ret = tail.data;
            tail.data = element;
        } else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            ret = p.data;
            p.data = element;
        }
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int indexOf(E element) {
        Node p = head;
        int index = 0;
        while (!p.data.equals(element)) {
            p = p.next;
            index++;
            if (p == head) {
        return -1;
    }
}
        return index;
                }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }


    @Override
    public boolean isEmpty() {
        return size == 0 && head == null && tail == null;
    }


    @Override
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void sort(Comparator<E> c) {
        if (c == null) {
            throw new IllegalArgumentException("comparator can not be null");
        }
        //插入排序来做
        if (size == 0 || size == 1) {
            return;
        }
        for (Node nodeA = head.next; nodeA != head; nodeA = nodeA.next) {
            E e = nodeA.data;
            Node nodeB;
            Node nodeC;
            for (nodeB = nodeA, nodeC = nodeB.pre; nodeC != tail && c.compare(nodeC.data, e) > 0; nodeB = nodeB.pre, nodeC = nodeC.pre) {
                nodeB.data = nodeC.data;
            }
            nodeB.data = e;
        }
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
            throw new IllegalArgumentException("0 <= fromIndex <= toIndex < size");
        }
        Node nodeA = head;
        for (int i = 0; i < fromIndex; i++) {
            nodeA = nodeA.next;
        }
        Node nodeB = head;
        for (int i = 0; i < toIndex; i++) {
            nodeB = nodeB.next;
        }
        Node p = nodeA;
        LinkedList<E> list = new LinkedList<>();
        while (true) {
            list.add(p.data);
            if (p == nodeB) {
                break;
            }
            p = p.next;
        }
        return list;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
        } else {
            Node p = head;
            while (true) {
                sb.append(p.data);
                if (p == tail) {
                    sb.append(']');
                    break;
                }
                sb.append(',');
                sb.append(' ');
                p = p.next;
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedListIterator();
    }

    class LinkedListIterator implements Iterator<E> {
        private Node cur = head;
        private boolean flag = true; //是否在第一圈

        @Override
        public boolean hasNext() {
            if (isEmpty()) {
                return false;
            }
            return flag;
        }

        @Override
        public E next() {
            E ret = cur.data;
            cur = cur.next;
            if (cur == head) {
                flag = false;
            }
            return ret;
        }
    }

    //双端队列的方法
    @Override
    public void addFirst(E element) {
        add(0, element);
    }

    @Override
    public void addLast(E element) {
        add(size, element);
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(size - 1);
    }

    @Override
    public E getFirst() {
        return get(0);
    }

    @Override
    public E getLast() {
        return get(size - 1);
    }

    //栈的方法
    @Override
    public void push(E element) {
        addLast(element);
    }

    @Override
    public E pop() {
        return removeLast();
    }

    @Override
    public E peek() {
        return getLast();
    }

    //队列的方法
    @Override
    public void offer(E element) {
        addLast(element);
    }

    @Override
    public E poll() {
        return removeFirst();
    }

    @Override
    public E element() {
        return getFirst();
    }
}

测试代码

package p0.测试;
import P3.链式结构.LinkedList;

import java.util.Comparator;


public class TestLinkedList {
    public static void main(String[] args) {
        //线性表
        LinkedList<Integer> list = new LinkedList<>();
        System.out.println(list);

        for (int i = 1; i <= 6; i++) {
            list.add((int) (Math.random() * 100));
        }
        System.out.println(list);
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        System.out.println(list);

        //栈
        list.push(55);
        System.out.println(list);
        System.out.println(list.pop());

    }
}

运行结果

?