> 摘要
>
> - 什么是线性表？
> - 线性表的分类
> - 顺序表，单链表，约瑟夫环，双向链表代码实现
# 线性表
## 什么是线性表？
由0个或多个元素组成的有限序列。
point：
- 序列=有序性
- 多个元素的线性表，第一个元素没有前驱，最后一个元素没有后继，其他元素有且仅有一个前驱，一个后继。
- 0个元素构成的线性表称为空表
<br>
## 线性表的分类
线性表分为顺序表，链表，其中链表又可分为单链表，双向链表
<br>
### 顺序表
- 采用顺序存储方式，其特点是逻辑上相邻的点物理上也相邻，插入删除效率低，查找效率高
- 基于数组实现
- 由于采用顺序存储方式，所以需要连续的存储空间，也就意味着长度必须是固定的。
<br>
### 单链表
- 采用链式方式存储，其特点是逻辑上相邻的点物理上并不一定相邻，插入删除效率高，查找效率低
- 链式存储是采用节点来进行存储的，每个节点包括data域和next域。
- 基于指针实现，但Java中是没有指针的。或者说，是C的变种指针，称为引用。与C不同的是，Java中的引用在考虑安全性的前提下，是不允许修改的。
- <br>
【网上看到了一个关于Java指针和C 的区别比喻】
在java中可以坐飞机到指定的目的地，但是你不能开飞机（安全）。但是在C 中可以自己开飞机（操作飞机）--具有危险性。
换句话说，Java中的指针只能被使用，而不能像C 中可以自由修改。
<br>
【如果Java中指针的引用是不可修改的，那么链表的插入删除操作导致的next域中引用的改变是如何实现的？】
指针应用的粒度过大，解决这个问题得从Java中对象的存储堆栈结构说起。
Java中通过堆栈来存储对象，栈中存放堆中对象的地址，堆中存放具体的对象，而堆的确是不可修改的，但栈中对象地址是可以修改的，而链表节点中next域中存放的正是栈中下个节点的对象地址。
<br>
### 双向链表
- 双向链表基于单链表，区别在于多了一个pre域指向前一个节点
- 单向列表只能从前往后查找，而双向链表可以向前向后查找。
## 一，顺序表代码实现
```
package com.company;
public class Linear_List {
private int[] arr;
private int size;
/**
* 初始化顺序表
* 顺序表基于数组实现，长度不可变，initial_size为初始化值
* @param initial_size
*/
public Linear_List(int initial_size) {
this.arr = new int[initial_size];
this.size = 0;
}
/**
* 判断顺序表是否满了
* @return
*/
public boolean isFull() {
if (this.size == arr.length) {
return true;
} else {
return false;
}
}
/**
* 判断顺序表是否为空
* @return
*/
public boolean isEmpty() {
if (this.size == 0) {
return true;
} else {
return false;
}
}
/**
* 1、增加元素
*
* @param value ：要插入的数据
* @param index ：插入的位置
*/
public void addData(int value, int index) {
if (isFull()) {
System.out.println("线性表已满");
} else if (index < 0 || index > arr.length) {
System. out.println("插入的下标越界，您要插入的下标为：" index);
} else {
for (int i = this.size - 1; i >= index; i--) {
arr[i 1] = arr[i]; //依次后移
}
arr[index] = value;
this.size ; //数组元素下标增加
}
}
/**
* 2、删除元素
*
* @param value ：要删除的数
*/
public void deleteData(int value) {
int pos = find(value);
if (pos == -1) {
System.out.println("您要找的 " value " 元素不在该线性表中");
} else {
System.out.println("您要删除的 " value " 元素下标为：" pos);
}
for (int j = pos; j <= this.size - 2; j ) { //这里-2，是因为找到的元素下标，要将后一个的冲掉前一个，会增加一个
arr[j] = arr[j 1];
}
this.size--;
}
/**
* 3、查找元素下标
*
* @param value ：所要查找的元素
* @return ：返回下标
*/
public int find(int value) {
int pos = -1;
if (isEmpty()) {
System.out.println("线性表已空，没有可删除元素");
} else {
for (int i = 0; i <= this.size - 1; i ) {
if (arr[i] == value) {
pos = i;
}
}
}
return pos;
}
/**
* 打印线性表元素
*/
public void print() {
for (int i = 0; i <= this.size - 1; i ) {
System.out.print(arr[i] " ");
}
System.out.println();
}
public static void main(String[] args) {
//初始化顺序表
Linear_List linear_list = new Linear_List(10);
for (int i = 0; i < 10; i ) {
linear_list.addData(i 1, i);
}
linear_list.print();
//删除
linear_list.deleteData(5);
System.out.println("删除后的线性表：");
linear_list.print();
//增加测试
System.out.println("添加元素：值为5，下标为1");
linear_list.addData(5, 1);
linear_list.print();
//查找元素下标
int find_value = 15;
int pos = linear_list.find(find_value);
if (pos == -1) {
System.out.println("您要找的 " find_value " 元素不在该线性表中");
} else {
System.out.println("您要找的 " find_value " 元素下标为：" pos);
}
}
}
```
## 二，单链表代码实现
```
import java.util.Stack;
//定义单个链表节点
class Node
{
public String data; //定义数据节点
public Node next; //定义指向下一个节点的指针
public Node(String data) {
this.data = data;
}
public Node() {
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Note{"
"data='" data '''
'}';
}
}
class Operation
{
//初始化头结点
private static Node head = new Node();
//插入节点（头插）
public void insertToHead(Node node)
{
//定义一个temp节点，保持头结点不动，方便测试
Node temp = head;
//头插法需要设置head.next和node.next的值。其指中nodeNext向headNext，而headNext指向node。
//由于是赋值的关系，二者顺序不可颠倒
node.next=temp.next;
temp.next=node;
}
//插入节点（尾插）
public void insertToLast(Node node)
{
Node temp = head;
while (true)
{
if(temp.next==null)
{break;}
temp=temp.next;
}
temp.next=node;
}
//插入节点（指定位置k之后）
public void insertToK(Node node,int k)
{
Node temp = head;
for(int i=0;i<k;i )
{
temp=temp.next;
}
node.next=temp.next;
temp.next=node;
}
//删除第m个节点
public void deleteM(int m)
{
Node temp = head;
for(int i=0;i<m-1;i )
{
temp=temp.next;
}
temp.next=temp.next.next;
}
//修改第n个节点（n）
public void updateN(int n)
{
Node temp = head;
for(int i=0;i<n;i )
{
temp=temp.next;
}
temp.data="up";
}
public static void main(String[] args)
{
Operation operation = new Operation();
//头插法
operation.insertToHead(new Node("A"));
operation.insertToHead(new Node("B"));
operation.insertToHead(new Node("C"));
//尾插法
operation.insertToLast(new Node("1"));
operation.insertToLast(new Node("2"));
operation.insertToLast(new Node("3"));
Node temp =head;
System.out.println("遍历链表：");
while(true)
{
if(temp.next==null)
{break;}
else
{
temp=temp.next;
System.out.println(temp.toString());
}
}
System.out.println();
/**
* 遍历链表，通过判断temp.next是否为空
*/
System.out.println("1.求单链表中有效节点个数.");
temp=head;
int count=0;
while(true)
{
if(temp.next==null)
{break;}
else
{
temp=temp.next;
count ;
}
}
System.out.println(count);
System.out.println();
/**
* 数学问题，获取链表总长，总长减去2就是倒数第三个的位置
*/
System.out.println("2.查找单链表中倒数第3个节点");
temp=head;
//获取链表总长
int length=0;
while (true)
{
if(temp.next==null)
{break;}
else
{
temp=temp.next;
length ;
}
}
//总长减去2就是倒数第三个的位置
temp=head;
for(int i=0;i<length-2;i )
{
temp=temp.next;
}
System.out.println(temp.data);
System.out.println();
/**
* 通过栈来实现，将链表节点全部压入栈中，再取出来
*/
System.out.println("3.从尾到头打印链表");
//把链表节点全部压入栈中，然后取出来
Stack<Node> stack = new Stack<>();
Node cur = head.next;
while (cur!=null)
{
stack.push(cur);
cur=cur.next;
}
while (stack.size()>0)
{
System.out.println(stack.pop());
}
System.out.println();
/**
* 定义三个辅助节点，上一个节点，当前节点，下一个节点
*
* 假设原链表结构
* head ---> A ---> B ---> C
*
* 第一次循环后:preNode=head;nextNode,curNode指向A
*
* 原始链表 head ---> A ---> B ---> C
反转链表 NULL<--- head
* preNode nextNode
* curNode
*
* 第二次循环后：preNode=A;nextNode,curNode指向B
*
*原始链表 head ---> A ---> B ---> C
反转链表 NULL<--- head<---A
preNode
* * nextNode
* * curNode
*
* 以此类推
* 最后一次循环
* 原始链表 head ---> A ---> B ---> C
反转链表 NULL<--- head<---A<----- B<---- C
* preNode
* nextNode
* curNode
*
* //preNode变成了表头
*/
System.out.println("4.实现单链表反转");
Node preNode = null;
Node curNode = head;
Node nextNode = null;
while (curNode!=null)
{
nextNode = curNode.next;
curNode.setNext(preNode);
preNode=curNode;
curNode=nextNode;
}
//preNode变成了表头
while(true)
{
if(preNode.next==null)
{break;}
else
{
System.out.println(preNode.toString());
preNode=preNode.next;
}
}
}
}
```
<br>
## 三，单向环形链表输出约瑟夫环
```
package com.company;
//定义单个节点
class Node
{
public String data; //定义数据节点
public Node next; //定义指向下一个节点的指针
public Node() {
}
public Node(String data) {
this.data = data;
}
@Override
public String toString() {
return "Note{"
"data='" data '''
'}';
}
}
public class Operation
{
//初始化头结点
private static Node head = new Node();
//尾插法
public void add(Node node)
{
Node temp = head;
while (true)
{
if(temp.next==null)
{break;}
temp=temp.next;
}
temp.next=node;
}
//创建单向环形链表
public Node createCircle(int n)
{
//创建单链表
for(int i=0;i<n;i )
{
add(new Node("No:" (i 1)));
}
System.out.println("遍历链表");
Node temp = head;
while(temp.next!=null)
{
temp=temp.next;
System.out.println(temp);
}
System.out.println();
//此时temp是链表最后一个节点
Node last = temp;
temp.next=head.next; //连接首尾
System.out.println("循环两遍单向环形链表：");
int count=2*n;
while(last!=null)
{
if(count==0)
{
break;
}
System.out.println(last.next);
last=last.next;
count--;
}
System.out.println("last=" last.data);
return last;
}
public static void JosephusProblem(int n, int k, int m, Node last)
{
//定位到第k个节点,输出k 1个节点并删除，并让last定位到第k个节点
Node temp = last;
for(int i=0;i<k;i ) //定位到第k个节点
{
temp=temp.next;
}
System.out.println("第一次输出" temp.next.data);//输出
temp.next=temp.next.next; //删除第K 1个节点
last=temp.next;
for(int i=0;i<n-1;i )
{
temp=last;
System.out.println("第二次输出" temp.next.data);
temp.next=temp.next.next;
last=temp.next;
}
}
public static void main(String[] args)
{
Operation operation = new Operation();
//定义人数
int n=5;
Node last = operation.createCircle(n);
//定义从第几个节点开始数
int k=1;
//定义数的次数
int m=2;
System.out.println();
System.out.println("输出约瑟夫环：");
JosephusProblem(n,k,m,last);
}
}
```
## 三，双向链表代码实现
```
import java.util.Stack;
//定义单个节点
class Node
{
public String data; //定义数据节点
public Node next; //定义指向下一个节点的指针
public Node pre; //定义指向上一个节点的指针
public Node() {
}
public Node(String data) {
this.data = data;
}
@Override
public String toString() {
return "Note{"
"data='" data '''
'}';
}
}
public class Operation
{
//初始化头结点
private static Node head = new Node();
//插入节点（尾插法）
public void addNode(Node node)
{
Node temp = head;
while(true)
{
if(temp.next==null)
{
break;
}
temp=temp.next;
}
temp.next=node;
node.pre=temp;
}
//插入节点(头插法)
public void addNodeToHead(Node node)
{
Node temp = head;
node.pre=temp;
node.next=temp.next;
temp.next.pre=node;
temp.next=node;
}
//插入到第k个节点后
public void addToK(Node node,int k)
{
Node temp = head;
for(int i=0;i<k;i )
{
temp=temp.next;
}
//先建立单链表联系
node.next=temp.next;
temp.next=node;
//建立pre指向
node.pre=temp;
node.next.pre=node;
}
//删除第n个结点
public void deleteNode(int n)
{
Node temp = head;
for(int i=0;i<n;i )
{
temp=temp.next;
}
temp.next.pre=temp.pre;
temp.pre.next=temp.next;
}
public void list()
{
//遍历链表
Node temp = head;
while(temp.next!=null)
{
temp=temp.next;
System.out.println(temp.toString());
}
System.out.println("=============");
}
//修改第m个结点
public void update(int m)
{
Node temp = head;
for(int i=0;i<m;i )
{
temp=temp.next;
}
temp.data="up";
}
public static void main(String[] args)
{
Operation operation = new Operation();
operation.addNode(new Node("A"));
operation.addNode(new Node("B"));
operation.addNode(new Node("C"));
operation.addNode(new Node("D"));
operation.addNodeToHead(new Node("head1"));
operation.addNodeToHead(new Node("head2"));
operation.addNodeToHead(new Node("head3"));
//遍历链表
operation.list();
System.out.println("删除第n个节点");
operation.deleteNode(3);
//遍历链表
operation.list();
System.out.println("修改第m个节点");
operation.update(3);
operation.list();
System.out.println("插入到第k个节点后");
operation.addToK(new Node("k" ),3);
operation.list();
}
}
```
<hr>
GitHub文章汇总：[JavaDev-Note](https://github.com/Noneplus/JavaDev-Note)
<br>
个人博客：[zkrun.top](zkrun.top)
