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

发表于 更新于 阅读次数：

前言

单向链表的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
package com;

public class LinkList<T> {

    private Node head;
    private int linkListLength;

    // 结点类
    private class Node {

        public T item;
        public Node next;

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

    }

    public LinkList() {
        // 初始化头节点
        this.head = new Node(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, 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, null);
        // 上一个节点指向新结点，新结点指向下一个节点
        nLeft.next = node;
        node.next = nRight;
        // 长度自增
        linkListLength++;
    }

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

    // 查找指定元素第一次出现在线性表中的索引
    public int indexOf(T t) {
        Node n = head;
        // 创建一个计数器，用来计算查找到的元素的索引
        int index = 0;
        while (head.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;
    }

}

完成

参考文献

哔哩哔哩——黑马程序员