1、链表的概述虽然顺序表的查询快，时间复杂度为O(1)，但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。
链表是一种物理存储单元上非连续，非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
链表由一系列的节点（链表中的每一个元素称为节点）组成，节点可以在运行时动态生成。
线性表的数据存储可以是顺序存储也可以是链式存储，按照存储方式的不同，可以把线性表分为顺序表和链表。
2、单向链表单向链表是链表的一种，它由多个节点组成，每个节点都由一个数据与和一个指针域组成；数据域存储数据，指针域用来指向其他后继节点。
链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的节点
如下图所示：
3、API设计类名
LinkList
构造方法
LinkList()：创建LinkList对象
成员方法
1. public void clear()：空置线性表2. public boolean isEmpty()：判断线性表是否为空，是返回true，否则反之3. public int length()：返回线性表中的元素个数4. public T get(int i)：读取并返回线性表中的第i个元素5. public void insert(T t)：往线性表中添加一个元素6. public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素7. public T remove(int i)：删除并返回线性表中第i个数据元素8. public int indexOf(T t)：返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
成员内部类
private class Node：节点类
成员变量
1. private Node head：记录首节点2. private int N：记录链表的长度
4、代码实现4.1 创建成员变量与节点类成员变量和节点类需要先进行创建，因为这两个东西是在链表中不可或缺的。
成员变量直接声明即可。
代码语言：javascript代码运行次数：0运行复制private Node head;// 记录头节点
private int N;// 元素个数4.1.1 节点类节点类可以用private修饰。毕竟只是在内部使用。
每个节点都需要有一个存储内容的变量，所以这里声明一个T泛型的item变量。
而每个节点都需要有指针，因为每个节点所指向的就是节点，所以这里声明一个Node节点类的next变量。
最后给这个类配置好构造方法即可。
代码语言：javascript代码运行次数：0运行复制private class Node
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
代码语言：javascript代码运行次数：0运行复制// 实现构造，初始化头结点和元素个数
public LinkListDemo(){
this.head = new Node(null,null);
this.N = 0;
}4.2.2 清除链表我们如何清除链表呢？我们知道链表由头节点开始，那么将头结点的指针清空不就清空链表了？
说着就做，将head头结点的指针改为null值，让它的指向为null。
同时，N记录元素个数的变量也改为0，都没内容了个数也要清空。
代码语言：javascript代码运行次数：0运行复制// 清除链表
public void clear(){
head.next = null;
this.N = 0;
}4.2.3 获得元素个数获取链表中的元素个数，直接返回N就好，因为N就是记录着链表中的元素个数的变量。
代码语言：javascript代码运行次数：0运行复制// 获得链表的元素总个数
public int length(){
return N;
}4.2.4 判断链表是否为空如何判断链表为空？我们只需要判断N变量是否为0就好了，如果链表元素个数为0，那么就会自动返回true
代码语言：javascript代码运行次数：0运行复制// 判断元素链表是否为空
public boolean isEmpty(){
return N==0;
}4.3 获得元素或元素所在位置4.3.1 根据索引获得元素方法中，由于传进来的是int类型也就是索引，那么我们可以根据该索引使用for循环进行遍历链表，但链表的遍历如何遍历？我们知道链表由头节点开始，那么我们也可以从头结点开始对下一个元素进行获取，当循环结束时，那么元素就找到了。
这里需要用辅助节点来记录循环得到的节点。
经过循环，o.next 赋值 o，最后返回o的内容即可。
代码语言：javascript代码运行次数：0运行复制// 根据索引得到元素
public T get(int i){
// 通过循环，从头节点开始往后找，依次找i次，既可找到对应的元素
Node o = head.next;
for (int index = 0;index o = o.next; } return (T) o.item; }4.3.2 获得元素首次出现在链表中的位置与查找元素类似，但在循环中要操作的步骤变多了，我们需要判断方法传入的内容与当前遍历元素的内容是否一致，如果一致那么元素就找到了。找到元素返回当前遍历的索引即可。 这里与查找元素不一样的是，在声明辅助节点变量时，不需要head.next，因为我们的索引是从0开始的，当然如果加上head.next把索引改为1即可。 在for循环内部判断内容元素是否一致，一致则返回当前循环的索引值 代码语言：javascript代码运行次数：0运行复制// 获得元素首次出现在链表中的位置 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++即可。 代码语言：javascript代码运行次数：0运行复制// 向链表中插入数据 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方法的遍历也是一致的，所以这里直接套用。 代码语言：javascript代码运行次数：0运行复制// 向表中的第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–即可。 第六步，返回索引处的元素内容 代码语言：javascript代码运行次数：0运行复制// 删除指定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) 相比较顺序表，链表的插入和移除的时间复杂度虽然一样，但是仍有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中设计到扩容等操作，同时它并没有涉及到元素的交换。 链表的查询操作性能会比较低，因此，如果我们的程序中查询操作比较多，建议使用顺序表；如果增删操作比较多，建议使用链表