【代码】线性表之双向链表

发表于 更新于 阅读次数：

前言

双向链表的Java版API实现

源代码

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
140
package com;

public class LinkList<T> {

    private Node head;
    private int linkListLength;

    // 结点类
    private class Node {

        public T item;
        public Node before;
        public Node next;

        public Node(T item, Node before, Node next) {
            this.item = item;
            this.before = before;
            this.next = next;
        }
    }

    public LinkList() {
        // 初始化头节点
        this.head = new Node(null, null, null);
        // 初始化元素个数
        this.linkListLength = 0;
    }

    // 清空线性表
    public void clear() {
        head.next = null;
        linkListLength = 0;
    }

    // 获取线性表的长度
    public int length() {
        return linkListLength;
    }

    // 判断顺序表是否为空
    public boolean isEmpty() {
        return linkListLength==0;
    }

    // 获取指定索引的元素
    public T get(int index) {
        Node n = head;
        for (int i = 0; i < index; i ++) {
            n = n.next;
        }
        return n.item;
    }

    // 向线性表末尾插入元素
    public void insert(T t) {
        Node n = head;
        // 获取末尾元素
        while (n.next!=null) {
            n = n.next;
        }
        // 创建一个新的元素，新元素的前驱是当前末尾元素
        Node node = new Node(t, n, null);
        // 将当前末尾元素的后驱设置为新元素
        n.next = node;
        // 长度自增
        linkListLength++;
    }

    // 向线性表指定索引插入元素
    public void insert(T t, int index) {
        Node nLeft = head;
        // 找到指定索引位置的前驱和后驱
        for (int i = 0; i < index-1; i ++) {
            nLeft = nLeft.next;
        }
        Node nRight = nLeft.next;
        // 创建新结点，并指向前驱和后驱
        Node node = new Node(t, nLeft, nRight);
        // 前结点的后驱和后结点的前驱都指向新结点
        nLeft.next = node;
        nRight.before = node;
        // 长度自增
        linkListLength++;
    }

    // 删除线性表指索引的元素
    public T remove(int index) {
        // 找到指定索引的前一个元素和它本身
        Node n = head;
        for (int i = 0; i < index; i ++) {
            n = n.next;
        }
        // 暂存一下需要删除的元素
        T t = n.item;
        /*
         * 判断它是不是最后一个元素
         *  如果是最后一个，就把它前一个元素的下一个元素设置为空
         *  如果不是最后一个，
         *      就把前驱元素的后驱元素设置为它的后驱元素，
         *      把后驱元素的前驱元素设置为它的前驱元素
         */
        if (n.next==null) {
            n.before.next = null;
        } else {
            n.before.next = n.next;
            n.next.before = n.before;
        }
        // 长度自减
        linkListLength--;
        return t;
    }

    // 查找指定元素第一次出现在线性表中的索引
    public int indexOf(T t) {
        Node n = head;
        // 创建一个计数器，用来计算查找到的元素的索引
        int index = 0;
        while (n.next!=null) {
            n = n.next;
            if (n.item.equals(t)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public String toString() {
        String str = "";
        Node n = head;
        while (n.next!=null) {
            n = n.next;
            str += n.item + " ";
        }
        return str;
    }



}

完成

参考文献

哔哩哔哩——黑马程序员