线性表
线性表在计算机中可以用顺序存储和链式存储两种存储结构来表示。
其中用顺序存储结构存储的叫做顺序表。
用链式存储结构表示的叫做链表。
顺序存储
地址连续
预先分配内存，可能会导致浪费
查改容易，直接通过下标就可以访问
增删不方便，每一次增加或者删除，后面的所有数据元素需要向前移动一位或者向后移动一位
代码实现
public static void main(String[] args)
{ //需要提前分配好空间
int array[]=new int[10]; for (int i = 0; i <array.length ; i++) { array[i]=i;
} //查找元素
System.out.println(array[2]); //修改元素
array[2]=666; //删除一个元素，后面的所有元素需要向前移动一位
for (int i = 2; i <9 ; i++) { array[i]=array[i+1];
}
}链式存储
可以动态增长长度
增删容易，不用将后面的数据元素进行移动，只需修改指针就行了。
查改不方便，需要从头开始遍历进行查找
几种链表
单向链表，每一个节点存放一个指针，只指向后一个节点或前一个节点
双向链表，每一个节点存放两个指针，一个指向前一个节点，一个指向后一个节点
循环链表，尾节点存放一个指针，指向首指针，形成回路
代码实现（单向链表）
public class Demo { public static void main(String[] args) throws Exception {
LinkList myList=new LinkList(); for (int i = 0; i < 10; i++) {
myList.insert(i,i);
}
myList.display();
System.out.println(myList.length());
myList.remove(1);
System.out.println(myList.get(1));
System.out.println(myList.indexOf(1));
}
}class Node{ public Object data; public Node next; public Node(Object data) { this.data=data;
} public Node() {}
}class LinkList{ public Node head; public LinkList() {
head=new Node();
} //清空链表
public void clear() {
head.next=null;
head.data=null;
} //判断是否为空
public boolean isEmpty() { return head.next==null;
} //获得链表长度
public int length() {
Node p=head.next; int length=0; while(p!=null)
{
length++;
p=p.next;
} return length;
} //按位序号查找
public Object get(int i)throws Exception {
Node p=head.next; int j=0; while(p!=null&&j<i)
{
p=p.next;
j++;
} if(j>i||p==null)
{ throw new Exception("第"+i+"个元素不存在");
} return p.data;
} //按值查找
public int indexOf(Object x) {
Node p=head.next; int j=0; while(p!=null&&!p.data.equals(x))
{
p=p.next;
j++;
} if(p==null) return -1; else
return j;
} //插入操作
public void insert(int i,Object x)throws Exception {
Node p=head; int j=-1; while(p!=null&&j<i-1)
{
p=p.next;
j++;
} if(j>i-1||p==null)
{ throw new Exception("第"+i+"个元素不存在");
} else
{
Node newNode=new Node(x);
newNode.next=p.next;
p.next=newNode;
}
} //删除操作
public void remove(int i)throws Exception {
Node p=head; int j=-1; while(p.next!=null&&j<i-1)
{
p=p.next;
j++;
} if(j>i-1||p.next==null) throw new Exception("删除位置不合法");
p.next=p.next.next;
} //输出所有节点
public void display() {
Node node=head.next; while(node!=null)
{
System.out.println(node.data);
node=node.next;
}
}
}运行结果
输出所有 0 1 2 3 4 5 6 7 8 9 链表长度为：10 删除第1号元素 输出所有 0 2 3 4 5 6 7 8 9 输出第1号元素 2 获取1的位置-1
顺序存储vs链式存储
没有哪一种数据结构更好，只有哪一种数据结构更适合某一种场景
对于查找较为频繁的宜用顺序表，因为他的查找时间复杂度为O(1)
对于增加删除较为频繁的宜用链式表，因为如果用顺序表，插入或者删除的时候后面的数据元素需要全部移动
空间上，顺序表需要提前分配好空间，这个时候可能浪费空间也可能空间不够，相对来说，链表更加灵活。
应用（经典的约瑟夫问题）
设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，杀掉报m的人，再从他的下一个人起重新报数，报到m时停止报数，报m杀掉，……，如此下去，直到最后剩下k个人为止。
用数组来做
import java.util.Scanner;public class 约瑟夫 { static int people,deleteNum,aliveNum; public static void f(int array[],int index,int nowPeople)
{ for(int i=0;i<people;i++)
{ //如果当前人数等于最后要求剩下的人数 跳出循环
if(nowPeople==aliveNum) return; //如果不为0表示该人未被杀掉
if(array[i]!=0)
{ //如果数到的数是7
if(index%deleteNum==0)
{ //标识为0 即杀掉
array[i]=0; //重新报数
index=1; //现存人数减一
nowPeople--;
} //如果当前报的数未被杀死 继续报数
else
index++;
}
}
f(array,index,nowPeople);
} public static void main(String[] args)
{
getData();
kill();
} /**
* kill
*/
public static void kill()
{ int array[]=new int [people]; for(int n=0;n<people;n++)
{ array[n]=n+1;
}
f(array,1,people); for(int n:array)
{ if(n!=0)
System.out.println(n);
}
} /**
* 获取用户输入的数据
*/
public static void getData()
{
Scanner in=new Scanner(System.in);
System.out.println("输入总人数");
people=in.nextInt();
System.out.println("数到第几个人删除");
deleteNum=in.nextInt();
System.out.println("最后剩下几个人");
aliveNum=in.nextInt();
}
}用双向链表
import java.util.Scanner;public class 约瑟夫环2 {
static int people,deleteNum,aliveNum; public static void main(String[] args) {
getData();
Node n=buildLink(); int index=1; int nowPeople=people; while(true)
{ //如果当前人数为最后要求剩下的人数 跳出
if(nowPeople==aliveNum) break;
//如果报到的数为前一位 即如果第七个数的人杀掉 那么报到6的时候，开始杀人
if(index==deleteNum-1)
{
n.next=n.next.next;
n=n.next; //重新报数
index=1;
//当前人数减一
nowPeople--;
} //如果不是 继续报数
else
{
n=n.next;
index++;
}
}
print(n);
}
// TODO 自动生成的方法存根
/**
* 获取用户输入的数据
*/
public static void getData()
{
Scanner in=new Scanner(System.in);
System.out.println("输入总人数");
people=in.nextInt();
System.out.println("数到第几个人删除");
deleteNum=in.nextInt();
System.out.println("最后剩下几个人");
aliveNum=in.nextInt();
} /**
* 创建链表
* @return
*/
public static Node buildLink()
{
Node head=new Node(1);
for (int i = 2; i < people+1; i++) {
head.addNode(new Node(i));
}
head.addNode(head); return head;
} /**
* 打印链表
* @param head
*/
public static void print(Node head)
{
Node currentNode=head; while(true)
{
System.out.print((Integer)currentNode.inner+" ");
currentNode=currentNode.next; if(currentNode==head) break;
}
System.out.println();
}
}两种方式对比
经过对比，可以发现，双向链表更容易理解，而且逻辑也更简单，所以说，选择一个正确的数据结构去解决问题是非常重要的。
我会讲完数据结构的大部分内容，下一篇将会讲讲栈和队列，哈哈，觉得对你有帮助的话，可以继续关注。
我觉得分享是一种精神，分享是我的乐趣所在，不是说我觉得我讲得一定是对的，我讲得可能很多是不对的，但是我希望我讲的东西是我人生的体验和思考，是给很多人反思，也许给你一秒钟、半秒钟，哪怕说一句话有点道理，引发自己内心的感触，这就是我最大的价值。（这是我喜欢的一句话，也是我写博客的初衷）
http://www.cnblogs.com/-new/p/7127892.html
更多精彩分享
- 陆老师 [海军工程大学 硕士 — 嵌入式开发专家] 2024-03-26 11:26:03.003
- 时光飞逝 2024-03-26 11:25:53.823
- 纸上得来终觉浅 2024-03-26 11:25:42.68
- 软件行业发展七大方向 2024-03-26 11:25:34.457
- 如何组建测试团队？ 2024-03-26 11:25:25.33
- 在青岛学习JavaEE哪家学校最好？ 2024-03-26 11:25:16.78
- 教务排课系统 2024-03-26 11:24:56.74
- 青岛帕特智能科技有限公司 2024-03-26 11:24:30.433
- 消息队列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26 11:24:15.657
- 感谢，我亲爱的万码学堂 2024-03-26 11:12:06.6
![陆老师 [海军工程大学 硕士 — 嵌入式开发专家]-Java培训机构,青岛Java培训,青岛计算机培训,软件编程培训,seo优化培训,网络推广培训,网络营销培训,SEM培训,网络优化,在线营销培训,Java培训](/uploadImages/20200701/1593572111851010992.jpg)
陆老师 [海军工程大学 硕士 — 嵌入式开发专家]