1、什么是线性表
首先，线性表是一种数据结构，是一种数据在逻辑上是连续的结构。
其次，线性表在计算机内部可以用顺序结构和链式结构存储数据。
顺序结构可以采用数组的方式完成，而本文主要描述的就是链式的线性表
2、什么是链表
链表是一个十分抽象的名词，但是开发者可以将其和火车结合进行理解，每一节车厢就是一个节点，而车厢与车厢之间的连接就是节点和节点之间的连接，但是在程序世界并不存在车厢与车厢那种的实际连接，因为程序世界的构成是内存，学过C/C++的开发者都知道，内存与内存的关系就是指针指向，那么就很好理解了。
接下来就一一展示一下
3、单链表
一、图解
单链表是一种最基础的链式线性结构，可以有头节点也可以没有头节点。
有头节点就是第一个节点中没有任何数据，但是指针指向下一个节点。
没有头节点就是第一个节点就直接存储数据
二、代码
1、链表类
package text;
public class Link {
private Node head;
//节点类使用内部类来声明实现
private class Node{
private int data;
private Node next;
public Node(int data,Node next){
this.data = data;
this.next = next;
}
}
//省略了get/set方法
}
}
2、单链表声明方法
一、添加节点
public void addNode(int data){
if(this.head == null){//如果头节点是null，则直接存入数据
this.head = new Node(data,null);
return;
}
Node current = this.head; //得到头节点，方便遍历链表
while(current.next != null){
current = current.next;
}
//遍历到最后一个节点之后就将新添加的数据加入到链表中
current.next = new Node(data,null);
}
二、删除节点
public void deleteNode(int index){
int nodeIndex = 1;
//两个指针一前一后进行遍历数组，方便删除元素
Node before = this.head.next, after = this.head;
while(before.next != null && nodeIndex != index){
nodeIndex++;//每遍历当到一个节点就使计数器加一，直到自增到符合条件就停止
after = before;
before = before.next;
}
//找到符合条件的下标后就删除
if(nodeIndex == index){
//当前节点的next就指向下一个节点的next，就能断开before的链接
after.next = before.next;
}
}
三、修改节点数据
public int repairElement(int index,int data){
int nodeIndex = 0;
Node temp = this.head;
while(temp != null){
//遍历节点找到合适的节点进行修改
if(nodeIndex == index){
temp.data = data;
return 1;
}
nodeIndex++;
temp = temp.next;
}
return -1;
}
4、查找指定的节点
public int searchElement(int index){
int nodeIndex = 0;
Node temp = this.head;
while(temp != null){
nodeIndex++;
if(nodeIndex == index){
return temp.data;
}
temp = temp.next;
}
return -1;
}
4、环形链表
一、图解
环形链表就是单链表的一种变化。
单链表的尾节点的next是指向null的。
环形链表的尾节点是指向头节点的。
二、代码
因为我写的环形链表类和单链表类大致相同，所以环形链表的代码就只展示与单链表代码的不同之处
1、添加节点
public void addNode(int data){
if(this.head == null){ //判断头节点是否为空，为空则直接在头节点存入数据
this.head = new Node(data, null);
return;
}
Node current = this.head;
while(current.next != null && !current.next.equals(head)){
current = current.next;
}
//初始化要新添加的节点，data为要存入的数据，this.head表示该节点指向头节点
Node temp = new Node(data,this.head);
current.next = temp;//尾节点的next指向新的节点
}
5、双向节点
一、图解
二、代码
1、链表代码
public class Link {
private Node head; //代表头节点
private Node foot;//代表尾节点
private class Node{
private int data;
private Node before; //指向前一个节点的指针
private Node next; //指向后一个的指针
public Node(int data,Node before,Node next){
this.data = data;
this.before = before;
this.next = next;
}
}
}
2、方法代码
一、添加节点
public void addNode(int data){
if(this.head == null){
//如果头节点为空，则将数据存入第一个节点，并且上一个节点和下一个节点都为null
this.head = new Node(data,null,null);
return;
}
Node temp = this.head;
while(temp.next!= null){
temp = temp.next;
}
//遍历到最后一个节点后就将新的数据添加到新的节点中，
temp.next = new Node(data,temp,null);//before指针指向前一个节点，next指向Null
foot = temp.next;
}
2、删除节点
public void deleteNode(int index){
int nodeIndex = 1;
Node before = this.head.next, after = this.head;
//两个指针一前一后遍历数组，便于删除
while(before != null && nodeIndex != index){
after = before;
before = before.next;
nodeIndex++;
}
if(nodeIndex == index){
//将后一个节点的next指向前一个节点的next就完成了before节点的断链，就删除了
after.next = before.next;
//将前一个节点的前一个节点的before指向after;
before.next.before = after;
}
}
3、遍历链表
一、从头部开始遍历
public void showElementByHead(){
Node temp = this.head;
while(temp != null){
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(temp.data);
temp = temp.next;
}
}
二、从尾节点开始遍历
public void showElementByFoot(){
Node temp = this.foot;
while(temp != null){
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(temp.data);
temp = temp.before;
}
}
总结
线性表是最基本的数据结构， 而链表是线性表中最重要的结构，也是日常中用的最多的线性结构，其实，线性表就是一开始理解的时候有点难度，理解好了之后就可以千变万化的写代码，
这还是扯一下数据结构和算法的核心——理解，很多同学都问过我“代码要背吗？”，要吗？？是不要的，
只有真正理解，才能将一个代码写得出神入化。