简单使用java创建出单向链表类

1、链表的概述

虽然顺序表的查询快，时间复杂度为O(1)，但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。

链表是一种物理存储单元上非连续，非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

链表由一系列的节点（链表中的每一个元素称为节点）组成，节点可以在运行时动态生成。

线性表的数据存储可以是顺序存储也可以是链式存储，按照存储方式的不同，可以把线性表分为顺序表和链表。

2、单向链表

单向链表是链表的一种，它由多个节点组成，每个节点都由一个数据与和一个指针域组成；数据域存储数据，指针域用来指向其他后继节点。

链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的节点

如下图所示：

3、API设计

4、代码实现

4.1 创建成员变量与节点类

成员变量和节点类需要先进行创建，因为这两个东西是在链表中不可或缺的。

成员变量直接声明即可。

private Node head;// 记录头节点
private int N;// 元素个数

4.1.1 节点类

节点类可以用private修饰。毕竟只是在内部使用。

每个节点都需要有一个存储内容的变量，所以这里声明一个T泛型的item变量。 而每个节点都需要有指针，因为每个节点所指向的就是节点，所以这里声明一个Node节点类的next变量。 最后给这个类配置好构造方法即可。

private class Node<T> {
    public T item;// 存储元素
    public Node next;// 指向下一个节点

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

4.2 初始化构造和基础信息获取

4.2.1 构造方法

我们的链表，需要在声明时就进行头结点和元素个数的初始化，意味着这需要一个构造方法

这里直接用this指向head和N进行初始化，节点为一个null节点，毕竟存储的内容不知道，也不知道指向谁。N为0

// 实现构造，初始化头结点和元素个数
public LinkListDemo(){
    this.head = new Node(null,null);
    this.N = 0;
}

4.2.2 清除链表

我们如何清除链表呢？我们知道链表由头节点开始，那么将头结点的指针清空不就清空链表了？

说着就做，将head头结点的指针改为null值，让它的指向为null。 同时，N记录元素个数的变量也改为0，都没内容了个数也要清空。

// 清除链表
public void clear(){
    head.next = null;
    this.N = 0;
}

4.2.3 获得元素个数

获取链表中的元素个数，直接返回N就好，因为N就是记录着链表中的元素个数的变量。

// 获得链表的元素总个数
public int length(){
    return N;
}

4.2.4 判断链表是否为空

如何判断链表为空？我们只需要判断N变量是否为0就好了，如果链表元素个数为0，那么就会自动返回true

// 判断元素链表是否为空
public boolean isEmpty(){
    return N==0;
}

4.3 获得元素或元素所在位置

4.3.1 根据索引获得元素

方法中，由于传进来的是int类型也就是索引，那么我们可以根据该索引使用for循环进行遍历链表，但链表的遍历如何遍历？我们知道链表由头节点开始，那么我们也可以从头结点开始对下一个元素进行获取，当循环结束时，那么元素就找到了。

这里需要用辅助节点来记录循环得到的节点。 经过循环，o.next 赋值 o，最后返回o的内容即可。

// 根据索引得到元素
public T get(int i){
    // 通过循环，从头节点开始往后找，依次找i次，既可找到对应的元素
    Node o = head.next;
    for (int index = 0;index<i;index++){
        o = o.next;
    }
    return (T) o.item;
}

4.3.2 获得元素首次出现在链表中的位置

与查找元素类似，但在循环中要操作的步骤变多了，我们需要判断方法传入的内容与当前遍历元素的内容是否一致，如果一致那么元素就找到了。找到元素返回当前遍历的索引即可。

这里与查找元素不一样的是，在声明辅助节点变量时，不需要head.next，因为我们的索引是从0开始的，当然如果加上head.next把索引改为1即可。 在for循环内部判断内容元素是否一致，一致则返回当前循环的索引值

// 获得元素首次出现在链表中的位置
public int indexOf(T t){
    // 从头节点开始，依次找到每一个节点和t比较
    Node n = head;
    for (int index = 0; n.next != null; index++) {
        n = n.next;
        if (n.item.equals(t)){
            return index;
        }
    }
    return -1;
}

4.4 插入元素

4.4.1 向链表中插入一个元素

如何插入一个元素呢？1. 我们需要找到当前链表的最后一个元素 2. 创建新节点 3. 让最后一个节点指向我们创建好的新节点即可 4. 元素个数+1

由于没有索引，所以用while循环从头开始遍历链表。当节点的下一个节点为空就停止遍历。 创建新节点，内容就是方法中传入的内容，指针为null毕竟是添加到链表末尾的元素。 老末尾元素的指针指向新节点进行赋值。 元素个数N++即可。

// 向链表中插入数据
public void insert(T t){
    // 找到当前最后一个节点
    Node n = head;
    while (n.next != null){
        n = n.next;
    }
    // 创建新节点，保存元素t
    Node newNode = new Node(t, null);
    // 让当前最后一个节点指向新节点
    n.next = newNode;
    // 元素的个数+1
    N++;
}

4.4.2 向表中指定元素前插入一个元素

由于方法中传入了i索引，所以我们可以根据i索引获得到对应的元素，步骤与在末尾插入元素是一致的，同时查找get方法的遍历也是一致的，所以这里直接套用。

// 向表中的第i处元素前插入t元素
public void insert(int i,T t){
    // 找到i位置的前一个节点
    Node pre = head;
    for (int index = 0; index <= i-1; index++) {
        pre = pre.next;
    }
    // 找到i位置的节点
    Node curr = pre.next;
    // 创建新节点，并且新节点要指向原来i位置的节点
    Node tNode = new Node(t, curr);
    // 原来i位置的前一个节点指向新节点
    pre.next = tNode;
    // 元素的个数+1
    N++;
}

4.5 删除指定索引处的元素

删除有以下步骤： 1.找到索引处的前一个元素 2.找到索引处的元素 3.找到元素的下一个元素 4.索引处的元素前一个元素指向元素的下一个元素 5.元素个数-1 6.返回元素

第一步的我们需要对链表进行遍历，与get方法的遍历不一样，由于获得的是前一个元素，所以辅助节点直接等于head头结点即可然后由它开始遍历。 第二步，找到前一个元素了直接.next就拿到了索引处的元素 第三步，找到索引处的元素直接.next就拿到了索引处元素的下一个元素 第四步，前一个元素指向下一个元素即可。 第五步，元素个数N–即可。 第六步，返回索引处的元素内容

// 删除指定i处的元素
public T remove(int i){
    // 找到i位置的前一个节点
    Node pre = head;
    for (int index = 0; index <= i-1; index++) {
        pre = pre.next;
    }
    // 找到i位置的节点
    Node curr = pre.next;
    // 找到i位置的下一个节点
    Node curr2 = curr.next;
    // 前一个节点指向下一个节点
    pre.next = curr2;
    // 元素个数-1
    N--;
    return (T) curr.item;
}

5.总结：

每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为：O(n) 每一次插入，需要先找到位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为：O(n) 每一次移除，需要先找到位置的前一个元素，然后完成移除操作，随着数据元素N的增多，查找的元素越多，时间复杂度为：O(n)

相比较顺序表，链表的插入和移除的时间复杂度虽然一样，但是仍有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中设计到扩容等操作，同时它并没有涉及到元素的交换。 链表的查询操作性能会比较低，因此，如果我们的程序中查询操作比较多，建议使用顺序表；如果增删操作比较多，建议使用链表