Java算法之双端链表和双向链表

双端链表

链表中保存着对最后一个链结点引用的链表。
可以方便的从尾结点插入数据。

代码

public class Node {
    // 数据域
    public long data;
    //指针域（保存下一个节点的引用）
    public Node next;

    public Node(long value) {
        this.data = value;
    }

    /**
     * 显示方法
     */
    public void display() {
        System.out.print(data + " ");
    }
}

/**
 * 双端链表
 */
public class DoubleEndLinkedList {
    // 头结点
    private Node first;
    //尾结点
    private Node last;

    public DoubleEndLinkedList() {
        first = null;
        last = null;
    }

    /**
     * 插入一个节点，在头结点后进行插入
     *
     * @param value
     */
    public void insertFirst(long value) {
        Node node = new Node(value);
        if (isEmpty()) {
            last = node;
        }
        node.next = first;
        first = node;
    }

    public void insertLast(long value) {
        Node node = new Node(value);
        if (isEmpty()) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
    }

    /**
     * 删除一个结点
     *
     * @return
     */
    public Node deleteFirst() {
        Node tmp = first;
        if (first.next == null) {
            last = null;
        }
        first = tmp.next;
        return tmp;
    }

    /**
     * 显示方法
     */
    public void display() {
        Node current = first;
        while (current != null) {
            current.display();
            current = current.next;
        }
    }

    /**
     * 查找方法
     *
     * @param value
     * @return
     */
    public Node find(long value) {
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        return current;
    }

    public Node delete(long value) {
        Node current = first;
        Node previous = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            previous = current;
            current = current.next;
        }
        if (current == first) {
            first = first.next;
        } else {
            previous.next = current.next;
        }
        return current;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return first == null;
    }
}

测试

public class TestDoubleEndLinkedList {
    public static void main(String[] args) {
        DoubleEndLinkedList listFirst = new DoubleEndLinkedList();
        listFirst.insertFirst(0);
        listFirst.insertFirst(1);
        listFirst.insertFirst(2);
        listFirst.display();
        System.out.println();
        listFirst.deleteFirst();
        listFirst.deleteFirst();
        listFirst.display();
        System.out.println();
        System.out.println("-----");
        DoubleEndLinkedList listLast = new DoubleEndLinkedList();
        listLast.insertLast(3);
        listLast.insertLast(4);
        listLast.insertLast(5);
        listLast.display();
        System.out.println();
        listLast.deleteFirst();
        listLast.display();
    }
}

结果

···
2 1 0
0

3 4 5
4 5
···

双向链表

双端链表可以方便的从尾结点插入数据，但是不能从尾部删除数据，所以引入双向链表。
双向链表每个结点除了保存对下一个结点的引用，同时还保存者前一个结点的引用。

代码

public class Node {
    // 数据域
    public long data;
    //指针域（保存下一个节点的引用）
    public Node next;
    //指针域（保存前一个节点的引用）
    public Node previous;

    public Node(long value) {
        this.data = value;
    }

    /**
     * 显示方法
     */
    public void display() {
        System.out.print(data + " ");
    }
}

/**
 * 双向链表
 */
public class DoubleByLinkedList {
    // 头结点
    private Node first;
    //尾结点
    private Node last;

    public DoubleByLinkedList() {
        first = null;
        last = null;
    }

    /**
     * 插入一个节点，在头结点后进行插入
     *
     * @param value
     */
    public void insertFirst(long value) {
        Node node = new Node(value);
        if (isEmpty()) {
            last = node;
        } else {
            first.previous = node;
        }
        node.next = first;
        first = node;
    }

    public void insertLast(long value) {
        Node node = new Node(value);
        if (isEmpty()) {
            first = node;
        } else {
            last.next = node;
            node.previous = last;
        }
        last = node;
    }

    /**
     * 删除一个结点,在头结点后进行删除
     *
     * @return
     */
    public Node deleteFirst() {
        Node tmp = first;
        if (first.next == null) {
            last = null;
        } else {
            first.next.previous = null;
        }
        first = tmp.next;
        return tmp;
    }

    /**
     * 删除一个结点,从尾部进行删除
     *
     * @return
     */
    public Node deleteLast() {
        if (first.next == null) {
            first = null;
        } else {
            last.previous.next = null;
        }
        last = last.previous;
        return last;
    }

    /**
     * 显示方法
     */
    public void display() {
        Node current = first;
        while (current != null) {
            current.display();
            current = current.next;
        }
    }

    /**
     * 查找方法
     *
     * @param value
     * @return
     */
    public Node find(long value) {
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        return current;
    }

    public Node delete(long value) {
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        if (current == first) {
            first = first.next;
        } else {
            current.previous.next = current.next;
        }
        return current;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return first == null;
    }
}

测试

public class TestDoubleByLinkedList {
    public static void main(String[] args) {
        DoubleByLinkedList dl = new DoubleByLinkedList();
        dl.insertLast(0);
        dl.insertLast(1);
        dl.insertLast(2);
        dl.display();
        System.out.println();
        while (!dl.isEmpty()){
            dl.deleteLast();
            System.out.println();
            dl.display();
        }
    }
}

结果

0 1 2 

0 1 
0