目录

双向链表

介绍

双向链表和单向链表不同在于节点多了一个指向前一个节点的指针,逻辑结构如下所示 https://gitee.com/lienhui68/picStore/raw/master/null/20200616170306.png 双向链表实现比较简单,直接给出代码

代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package com.eh.ftd.dsa.ds.impl;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/16 17:03
 */
public class DoubleLinkedList<E> {

    private Node<E> head = new Node();

    static class Node<E> {
        private E e;
        private Node pre;
        private Node next;

        public Node() {
        }

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

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    '}';
        }
    }

    // 从尾部增加一个节点
    public boolean addLast(E e) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        Node node = new Node(e, temp, null);
        temp.next = node;
        return true;
    }

    // 从头部增加一个节点
    public boolean addFirst(E e) {
        Node node = new Node(e, head, head.next);
        node.next = head.next;
        head.next = node;
        return true;
    }

    // 查找一个节点
    public E find(Object o) {
        Node temp = head.next;
        while (temp != null) {
            if (o.equals(temp.e)) {
                return (E) temp;
            }
            temp = temp.next;
        }
        return null;
    }

    // 删除一个节点
    public boolean remove(Object o) {
        Node temp = head.next;
        while (temp != null) {
            if (o.equals(temp.e)) {
                temp.pre.next = temp.next;
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    // 删除一个头节点
    public void removeFirst() {
        if (head.next == null) {
            return;
        }
        head.next = head.next.next;
    }

    // 删除一个尾节点
    public void removeLast() {
        if (head.next == null) {
            return;
        }
        Node temp = head.next;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.pre.next = null;
    }

    /**
     * 用来演示
     */
    public void display() {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
            System.out.println(temp.e);
        }
    }

    public static void main(String[] args) {
        DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
        System.out.println("======演示尾插法======");
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.display();
        System.out.println("======演示头插法======");
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.display();
        System.out.println("======演示查找======");
        System.out.println(list.find(3));
        System.out.println("======演示从头部删除======");
        list.removeFirst();
        list.display();
        System.out.println("======演示从尾部删除======");
        list.removeLast();
        list.display();
        System.out.println("======演示删除一个元素======");
        list.remove(2);
        list.display();
    }
}


运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200616173553.png