1.什么是链表？
一：链表是什么
1、链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成。
2、结点包括两个部分：（1）存储数据元素的数据域（内存空间），（2）存储指向下一个结点地址的指针域。
3、相对于线性表顺序结构，操作复杂。
4.链表分为 （1）单链表 （2）双链表 （3）单向循环链表 （4）双向循环链表
画个图让大家更好理解两者的优缺点
2.单链表的基本功能和结构
public class Linklist<T> { //记录头结点 private Node head; //记录链表的长度 private int N; //结点类 private class Node{ //存储数据 T item; //下一个结点 Node next; public Node(T item, Node next){ this.item=item; this.next=next; } } //构造方法 public Linklist() { //初始化元素个数 this.N=0; //初始化头结点 this.head=new Node(null,null); }
解析： 单链表需要一个头结点和一个int类型的变量N记录元素的个数。因为一个结点需要有数据域和指针域，所以我们单链表内需要有一个内部类Node表示结点。因为我们还不能确定存放的数据类型，所以用泛型T表示存放的数据类型的成员变量，因为next指的是下一个结点，所以需要一个Node类型的成员变量。链表的构造方法刚开始没有元素所以让N为0，头结点head的数据域不存放元素所以为null，还没有插入元素所以它的next也为null
下面是单链表需要实现的基本API
public void clear() 清空链表 public int getN() 获取链表的长度 public boolean isEmpty() 判断链表是否为空 public T get(int i) 获取指定位置i的元素 public void add(T t) 向链表中添加元素t public void insert(int i,T t) 向指定位置i处添加元素 public T remove(int i) 删除指定位置处i处的元素,并返回被删除的元素 public int indexOf(T t) 查找元素第一次出现的位置 public void reverse() 用来反转整个链表
3.单链表基本功能代码具体实现
1.清空链表，获取链表长度，判断链表是否为空
//清空链表 public void clear(){ head.next=null; this.N=0; } //获取链表的长度 public int getN(){ return N; } //判断链表是否为空 public boolean isEmpty(){ return N==0; }
解析：因为链表的查询需要从头结点一个个next查找下去，如果头结点的next直接为null，那我们就什么也查不到了，链表就变成空，同时让N为0。获取链表的长度直接返回N的值即可。判断链表是否为空我们返回N是否等于0即可。
2.获取指定位置的元素
//获取指定位置i的元素 public T get(int i){ //通过循环，从头结点往后找 Node n=head.next; for (int j = 0; j <i; j++) { n=n.next; } return n.item; }
解析：我们首先建立一个Node结点n并将它赋值为头结点的下一个结点，通过for循环，我们一个一个遍历下去直到找到我们指定的位置i。这里我们要注意循环的判定条件，我们走一次循环就走一个结点，因为我们是从第一个结点开始，所以需要走i-1次循环，如果你的n设的是head，那我们就要走i次循环，判定条件应为j<=i。
3.像链表中添加元素t
//向链表中添加元素t public void add(T t){ //找到当前最后一个结点 Node n=head; while (n.next!=null){ n=n.next; } //创建新节点保存元素 Node node = new Node(t,null); n.next=node; //元素个数加1 N++; }
解析：添加元素，我们需要找到最后一个结点，此时它的next是null，我们设一个结点n赋值为头结点，用while循环不断更新为下一个结点，当它的下一个结点为null时说明我们n已经成为了最后一个结点。得到最后一个结点后我们新建立一个结点node，它的数据域填充我们的需要插入的元素t，让它接在我们的最后一个结点后，然后让N加一，我们的添加就完成了。要在尾部添加元素，单链表必须要从头遍历到尾部，在这方面单链表比不上顺序表。但插入到具体的位置的操作单链表却具有顺序表不具有的优点。
