java数据结构实现双向链表功能

1
2
3
4
5
6
public interface MyList<E> {
    void add(E node);
    E get(int index);
    E remove(int index);
    int size();
}

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
137
138
139
public class MyDoublyLinkList<E> implements MyList<E> {

    /**
     * 定义双向链表节点
     */
    class Node<E> {
        Node<E> prev;
        E item;
        Node<E> next;

        public Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }

    private Node<E> head;
    private Node<E> tail;
    private int size;

    /**
     * 将节点添加到尾部
     *
     * @param item
     * @return
     */
    @Override
    public void add(E item) {
        this.linkLast(item);
    }

    /**
     * 添加一个元素到尾部
     *
     * @param e
     */
    private void linkLast(E e) {
        //获取tail
        Node<E> node = this.tail;
        //创建一个node
        Node<E> newNode = new Node<>(node, e, null);
        this.tail = newNode;
        if (node == null)
            this.head = newNode;
        else
            node.next = newNode;
        size++;
    }

    /**
     * 获取指定位置元素
     * @param index
     * @return
     */

    @Override
    public E get(int index) {
        //校验index是否合法
        checkIndex(index);
        //获取index元素
        return getNode(index).item;
    }

    /**
     * 校验index合法性
     *
     * @param index
     */
    private void checkIndex(int index) {
        if (!(index >= 0 && index < this.size))
            throw new IndexOutOfBoundsException(String.format("index out of bounds,index:%s,size:%s", index, this.size));
    }

    /**
     * 获取node
     *
     * @param index
     * @return
     */
    private Node<E> getNode(int index) {
        if (index > (size >> 1)) {
            Node<E> node = this.tail;
            //从tail向前遍历
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        } else {
            //从head向后遍历
            Node<E> node = this.head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }
    }

    /**
     * 删除指定位置元素
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        //判断index合法性
        this.checkIndex(index);
        Node<E> node = getNode(index);
        E e = node.item;
        //判断是否为头节点
        if (node.prev == null) {
            this.head = node.next;
        } else {
            node.prev.next = node.next;
            node.prev = null;
        }
        //判断是否为尾节点
        if (node.next == null) {
            this.tail = node.next;
        } else {
            node.next.prev = node.prev;
            node.next = null;
        }
        node.item = null;
        size--;
        return e;
    }

    /**
     * 获取链表长度
     *
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
        MyList<String> stringMyList = new MyDoublyLinkList<>();
        System.out.println(stringMyList.size());
        stringMyList.add("a");
        stringMyList.add("b");
        stringMyList.add("c");
        stringMyList.add("d");
        System.out.println(stringMyList.size());
        String re = stringMyList.remove(1);
        System.out.println(re);
        for (int i = 0; i < stringMyList.size(); i++) {
            System.out.println(stringMyList.get(i));
        }
    }