数据结构和算法-5.2-双端链表&双向链表

双端链表

• 单链表要想在表尾插入一个链结点，需要遍历整个链表直到表尾，再进行插入，效率很低；
• 双端链表增加了对表尾链结点的引用，可以直接在表尾插入链结点；
• 下面是双端链表的实现

public class FirstLastLinkList<T> {
    private Link<T> first;
    private Link<T> last;

    public boolean isEmpty(){
        return first==null;
    }

    public void insertFirst(T value){
        Link<T> newLink=new Link<>(value);
        if (isEmpty())
            last=newLink;
        newLink.next=first;
        first=newLink;
    }

    public void insertLast(T value){
        Link<T> newLink=new Link<>(value);
        if (isEmpty())
            first=newLink;
        else
            last.next=newLink;
        last=newLink;
    }

    public Link<T> deleteFirst(){
        Link temp=first;
        if (first.next==null)
            last=null;
        first=first.next;
        return temp;
    }

    public void display() {
        System.out.print("LinkList:{ ");
        Link current = first;
        while (current != null) {
            current.display();
            if (current.next != null)
                System.out.print(", ");
            current = current.next;
        }
        System.out.println("} ");
    }
}

• 双端链表的使用

private static void testFirstLastLinkList() {
        FirstLastLinkList linkList = new FirstLastLinkList();
        for (int i = 0; i < 10; i++) {
            if (i % 2 == 0)
                linkList.insertFirst("data_" + i);
            else
                linkList.insertLast("data_" + i);
            linkList.display();
        }

        linkList.deleteFirst();
        linkList.deleteFirst();
        System.out.println(">>执行两次deleteFirst<<");
        linkList.display();

    }

• 之前有介绍用数组实现队列，下面提供一个用双端链表实现的队列, 其中Queue是队列的基类，若有疑惑，可以先看一下前面讲队列的文章；

public class LinkQueue<T> extends Queue<T> {

    private FirstLastLinkList<T> linkList;

    public LinkQueue() {
        linkList=new FirstLastLinkList<>();
    }

    @Override
    public boolean isEmpty() {
        return linkList.isEmpty();
    }

    @Override
    public void insert(T value) {
        linkList.insertLast(value);
    }

    @Override
    public T remove() {
        return linkList.deleteFirst().data;
    }

    @Override
    public void display() {
        System.out.print("LinkQueue: ");
        linkList.display();
    }
}

双向链表

• 传统链表存在的问题: 沿链表反向遍历比较困难,很难取得前一个链结点
• 关键点: 每个链结点有两个指向其他链结点的引用,而不是一个
• 缺点: 每次插入或删除一个链结点时,要处理四个链结点的应用,而不是两个
• 可以用来实现双端队列
• 双向链表的实现：

1. 首先要重新定义一个链结点类，双向链表的链结点需要保存左右两个元素的引用

public class DoublyLink<T>  {
    public T data;//数据域
    public DoublyLink<T> left;//指针域, 指向前一个链结点
    public DoublyLink<T> right;//指针域, 指向后一个链结点

    public DoublyLink(T data) {
        this.data = data;
    }

    public void display(){
        System.out.print("DoublyLink:{"+data.toString()+"}");
    }
}

2. 双向链表的实现

public class DoublyLinkList<T> {
    private DoublyLink<T> first;
    private DoublyLink<T> last;

    public boolean isEmpty() {
        return first == null;
    }

    public void insertFirst(T value) {
        DoublyLink<T> newLink = new DoublyLink<>(value);
        if (isEmpty())
            last = newLink;
        else
            first.left = newLink;
        newLink.right = first;
        first = newLink;
    }

    public void insterLast(T value) {
        DoublyLink<T> newLink = new DoublyLink<>(value);
        if (isEmpty())
            first = newLink;
        else {
            last.right = newLink;
            newLink.left = last;
        }
        last = newLink;
    }

    /**
     * 在key后插入value
     *
     * @param key
     * @param value
     * @return
     */
    public boolean insertAfter(T key, T value) {
        DoublyLink<T> current = first;
        while (current.data != key) {
            current = current.right;
            if (current == null) {
                return false;
            }
        }
        DoublyLink<T> newLink = new DoublyLink<>(value);
        if (current == last) {
            newLink.right = null;
            last = newLink;
        } else {
            newLink.right = current.right;
            current.right.left = newLink;
        }
        newLink.left = current;
        current.right = newLink;
        return true;
    }

    public DoublyLink<T> deleteFirst() {
        DoublyLink temp = first;
        if (first.right == null)
            last = null;
        else
            first.right.left = null;
        first = first.right;
        return temp;
    }

    public DoublyLink<T> deleteLast() {
        DoublyLink temp = last;
        if (first.right == null)
            first = null;
        else
            last.left.right = null;
        last = last.left;
        return temp;
    }

    public DoublyLink<T> delete(T value) {
        DoublyLink<T> current = first;
        while (current.data != value) {
            current = current.right;
            if (current == null)
                return null;
        }

        if (current == first)
            first = current.right;
        else
            current.left.right = current.right;

        if (current == last)
            last = current.left;
        else
            current.right.left = current.left;

        return current;
    }

    public void displayForward() {
        System.out.print("DoublyLinkList(first-->last): ");
        DoublyLink<T> current = first;
        while (current != null) {
            current.display();
            current = current.right;
        }
        System.out.println();
    }

    public void displayBackground() {
        System.out.print("DoublyLinkList(last-->first): ");
        DoublyLink<T> current = last;
        while (current != null) {
            current.display();
            current = current.left;
        }
        System.out.println();
    }
}

• 双向链表的使用

private static void testDoublyLinkList() {
        DoublyLinkList<String> linkList = new DoublyLinkList<>();

        linkList.insertFirst("v_3");
        linkList.insertFirst("v_2");
        linkList.insertFirst("v_1");
        linkList.displayForward();
        linkList.displayBackground();

        linkList.insterLast("v_101");
        linkList.insterLast("v_102");
        linkList.insterLast("v_103");
        linkList.insertAfter("v_3", "v_6");
        linkList.insertAfter("v_3", "v_5");
        linkList.insertAfter("v_3", "v_4");
        linkList.displayForward();
        linkList.displayBackground();

        linkList.deleteFirst();
        linkList.deleteLast();
        linkList.delete("v_6");
        linkList.displayForward();
        linkList.displayBackground();
    }