CoderHann

单向链表的实现

发表于 | 分类于 ， | | 阅读次数

单链表简介


单链表的结构如上，有别于连续存储在内存中的数组，是一种以链式形式的存储结构。下面详细介绍下该链表中存在的元素：
结点：构成单向链表的基本单元我们称为结点，其中每个结点都有一个data区和一个结点指向区。data区就是存放数据的地方，一般存储基本类型数据或者引用对象的地址，结点指向区存储下一个结点的地址。
头结点：指向单链表中的第一个结点，即首结点。
尾结点：指向单链表中的最后一个结点。
链表长度：记录链表中存在的结点个数，即我们存储的数据个数。

单链表的实现

链表的基本介绍如上，下面我们需要根据代码来进行说明。本博客主要流程示例代码使用java语言，每块代码前都标示是属于哪个java文件下的哪个类。废话不多开始！！！

结点类的创建

创建链表的基本单元结点类如下，该类提供了数据存储区和接点指向区，还提供了便捷的构造函数，以及结点操作的相关方法：

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
// SingleLinkedList.java
// class Node<E>
class Node<E> {
    /**
     * 数据区
     */
    public E data;
    /**
     * 下一个结点引用
     */
    public Node<E> next;
    public Node(E e) {
        data = e;
        next = null;
    }
    /**
     * 判断该结点后是否有下一个结点
     * @return
     */
    public boolean hasNext() {
        return this.next != null;
    }
}

单链表类的创建

单链表类SingleLinkedList主要用于对数据的添加、删除、打印，反转等功能，下面是SingleLinkedList的主要成员变量的介绍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// SingleLinkedList.java
// class SingleLinkedList<E>
public class SingleLinkedList<E> {
    /**
     * 存储结点数量
     */
    private int length;
    /**
     * 头结点引用
     */
    private Node<E> header;
    /**
     * 尾结点引用
     */
    private Node<E> footer;
}

添加功能
上面是SingleLinkedList数据成员的代码，这里我们给它加入添加功能的方法，添加方法分为了两种，一种是直接在链表尾部添加一个数据，另一个是在指定位置结点的后面添加一个数据。

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
/**
 * 在链表最后的位置添加对象
 * @param e 泛型对象
 */
public void add(E e) {
    Node<E> indexNode = footer;
    try {
        addElement(indexNode,new Node<>(e));
    } catch (Exception e1) {
        e1.printStackTrace();
    }
}
/**
 * 在index位置的对象后面添加对象
 * @param index 索引从0开始，0表示在首结点前面添加，1表示header
 * @param e 泛型对象
 */
public void add(int index,E e) {
    Node<E> indexNode = null;
    try {
        indexNode = getNode(index);
        addElement(indexNode,new Node<>(e));
    } catch (Exception e1) {
        e1.printStackTrace();
    }
}
/**
 * 添加对象的集中处理代码块
 * @param frontElement 在这个对象上执行添加操作
 * @param element 要添加的对象
 */
private void addElement(Node<E> frontElement,Node<E> element) throws Exception{
    if (element.data == null) {
        throw new Exception("添加数据为空");
    }
    if (frontElement == null) {
        if (header != null) { //插入位置为0，链表不为空
            element.next = header;
            header = element;
        } else { //链表长度为0，在首位添加数据
            header = element;
        }
    } else {
        element.next = frontElement.next;
        frontElement.next = element;
    }
    if (!element.hasNext()) {
        footer = element;
    }
    length++;
}

我们来详细的来看下这三个方法：
1.private void addElement(Node<E> frontElement,Node<E> element):这个是添加数据的核心处理方法，该方法接收要添加的结点的前一个结点，以及要添加的结点，如果链表为空，或者想再链表的头部添加结点时frontElement为空。这种情况的添加要操作header的指向；还有种情况是frontElement有值，说明是在链中或者链尾添加数据，那就将frontElement.next给到新结点的next，然后新结点追加上在frontElement.next上即可。这里面还有个注意点是关于尾结点的更改，如过新添加的结点的next是null值的话，说明该添加的结点取代了原来的尾结点，需要重设footer的引用对象。
2.public void add(E e):这个是在链表的尾部添加e数据，调用addElement方法传递的尾结点的引用以及新值。
3.public void add(int index,E e):该方法是在index位置的结点后面添加新的元素，里面主要是获取了index所在的结点，然后传值给核心方法addElement。

删除功能
删除功能也提供了两种方式：一个将index所在的数据删除，另一种是将对象地址相同的对象删除。除了这两个方法还提供了一个集中处理删除操作的方法，以下是代码的展示。

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
/**
 * 链表的删除操作 索引
 * @param index 将要删除的对象索引 （1-length）
 * @return 删除掉的对象
 */
public E delete(int index) {
    if (index < 1 || index > this.length) {
        return null;
    }
    Node<E> deletedNode = null;
    Node<E> indexNode = header;
    Node<E> frontNode = null;
    while (index > 0) {
        if (index == 1) {
            deletedNode = deleteElement(frontNode,indexNode);
            break;
        }
        index--;
        frontNode = indexNode;
        indexNode = indexNode.next;
    }
    return deletedNode.data;
}
/**
 * 链表的删除操作 指定对象
 * @param e 将要删除的对象
 * @return 删除掉的对象
 */
public E delete(E e) {
    Node<E> deletedNode = null;
    Node<E> indexNode = header;
    Node<E> frontNode = null;
    while (indexNode != null) {
        if (indexNode.data == e) {
            deletedNode = deleteElement(frontNode,indexNode);
            break;
        }
        frontNode = indexNode;
        indexNode = indexNode.next;
    }
    return deletedNode.data;
}
/**
 * 删除操作集中处理
 * @param frontElement 前一个对象Node
 * @param element 要删除的对象Node
 * @return 删除掉的对象Node
 */
private Node<E> deleteElement(Node<E> frontElement,Node<E> element) {
    Node<E> deletedNode = element;
    Node<E> preNode = null;
    if (frontElement == null) {
        header = element.next;
        preNode = null;
    } else {
        frontElement.next = element.next;
        preNode = frontElement;
    }
    if (!deletedNode.hasNext()) {
        footer = preNode;
    }
    length--;
    return deletedNode;
}

现在对这三个方法进行详细介绍：
1.private Node<E> deleteElement(Node<E> frontElement,Node<E> element):该方法是删除功能的核心方法，跟添加功能的核心方法类似都有两个参数，分别对应要删除的结点的前一个结点和要删除的结点。删除功能相对于添加要容易一点把删除头结点的区分开来就ok，即frontElement为null时表示要删除头结点，操作header的指向为header.next即可。frontElement有值时执行frontElement.next为要删除结点的下一个element.next即可。还有就是删除的结点如果next为空时说明删除的是尾结点，需要调整footer的引用为frontElement。
2.public E delete(int index):删除index处的数据，并将这个数据返回。主要是获取删除方法需要的两个参数。
3.public E delete(E e):删除数据e,如果e不存在该方法的调用不会骑任何作用。

链表的反转
链表的反转即将链表原有的数据顺序以及指向颠倒下，请先看源码实现：

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
/**
 * 链表的反转[A,B,C,D]->[D,C,B,A]
 */
public void reverseSingleLinkedList() {
    Node<E> firstElement = header;
    reverse(firstElement);
    Node<E> tempElement = header;
    header = footer;
    footer = tempElement;
    footer.next = null;
}
private void reverse(Node<E> currentElement) {
    Node<E> nextElement = currentElement.next;
    if (nextElement.hasNext()) {
        reverse(nextElement);
    }
    nextElement.next = currentElement;
}

单链表的反转其实可以看做是数据上的逆序，举个列子列表内有四个数据分别是[A->B->C->D->null]逆序后为[D->C->B->A->null]。下面我们看看上面的两个方法都做了什么事情：
1.private void reverse(Node<E> currentElement):该方法内部采用递归方式将数据分散开为A、B、C、D。然后进行逆序指向，即D->C->B->A->B。这个是调用完该方法后的指向。其中存在的问题是header指向的是A，footer指向的是D，还有A的下一个指向为B。
1.public void reverseSingleLinkedList():这个方法除了调用reverse方法外还要对上面的存在的问题进行处理，先进行header和footer的更改，然后将footer的下一个指向null。最终将变成D->C->B->A->null的顺序。

其它的方法
单链表的核心方法上面已经介绍过了，下面把剩下的其它代码贴出来分别是获取指定index上的实例数据public E getObject(int index)、结点数据private Node<E> getNode(int index) throws Exception以及遍历链表的方法public void printSingleLinkedList()。

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
/**
 * 获取指定索引位置的对象
 * @param index 索引
 * @return 链表存储的对象
 */
public E getObject(int index) {
    if (index < 1 || index > this.length) {
        return null;
    }
    Node<E> node = null;
    try {
        node = getNode(index);
    } catch (Exception e) {
        e.printStackTrace();
    }
    return node.data;
}
/**
 * 获取对应index的结点对象element
 * @param index 指定索引
 * @return Node<E> 对象
 * @throws Exception
 */
private Node<E> getNode(int index) throws Exception{
    if (index < 0 || index > this.length) {
        throw new Exception("索引值越界");
    }
    Node<E> node = null;
    if (index == 0) {
        return node;
    }
    Node<E> indexNode = header;
    for (int i = 0;i < index - 1;i++) {
        indexNode = indexNode.next;
    }
    node = indexNode;
    return node;
}
/**
 * 打印单链表的数据
 */
public void printSingleLinkedList() {
    Node<E> node = header;
    System.out.print("SingleLinkedList:[");
    while (node != null) {
        System.out.print(node.data);
        if (node.hasNext()) {
            System.out.print(",");
        }
        node = node.next;
    }
    System.out.println("]");
}

总结

单向链表是由一个个结点有顺序的链接而成的结点列表，第一个结点有header指向是头结点最后一个结点由footer指向是尾结点。更普通的线性结构的数组比较起来具有以下的优点：结点的添加(插入)、删除比较方便，不需要移动数据只需要更新下一个结点指向即可；除此之外链表在空间利用上更好点不需要占用较大的连续存储空间；当然也会有缺点：查询的操作没有线性表的效率高。所以在使用这两种结构时要根据需求决定，如果插入和删除数据比较多的用单链表比较合适，查询比较多的用线性数组要好点。

附加

更多相关内容请前往内功修炼系列！！！