线性表
线性表（linear list）是n个具有相同元素的有限序列，线性表是实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就是说是一条连续的直线，但是在物理结构上不一定是连续的，线性表在物理上存储时，通常是以数组和链式结构形式存储。
顺序表
概念：
顺序表是一段物理地址连续的存储单元依次存储的线性结构，一般情况下采用数组存储，在数组上完成增删改查。
顺序表一般可分为：
静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于已知存储数据多少的场景，如果静态定长n值过大了，空间开大了浪费，开少了不够用，相比之下动态顺序表更灵活，根据需要动态的分配大小。
话不多说，用代码带你们了解动态顺序表
import java.util.Arrays;
public class Sequenlist {
public int[] elem;
public int useSize;
//初始值给个5的大小
public Sequenlist(){
this.elem=new int[5];
}
//判断顺序表是否满
public boolean isFull(){
if(this.useSize==this.elem.length){
return true;
}
return false;
}
//插入操作
public void add(int pos,int val){
if(isFull()){
System.out.println("顺序表满了，自动进行扩容");
this.elem=Arrays.copyOf(this.elem,this.elem.length*2);
}
if(pos<0||pos>this.useSize){
System.out.println("位置非法");
return;
}
//这是在顺序表最后位置插入
if(pos==this.useSize){
this.elem[pos]=val;
this.useSize++;
return;
}
//中间或开头插入的情况
for(int i=this.useSize-1;i>=pos;i--){
this.elem[i+1]=this.elem[i];
}
this.useSize++;
this.elem[pos]=val;
}
//删除某个位置的元素的值
public void delete( int pos){
if(pos<0||pos>this.useSize){
System.out.println("位置非法");
}
//将需要删除的值移动到数组最后，最后与空值交换
for(int i=pos;i<this.useSize;i++){
this.elem[i]=this.elem[i+1];
}
this.useSize--;
}
//查找某个元素对应位置
public int search(int find){
for(int i=0;i<this.useSize;i++){
if(find==this.elem[i]){
return i;
}
}
return -1;
}
//得到某个位置对应的元素的值
public int getpos(int pos){
if(pos<0||pos>this.useSize){
System.out.println("位置非法");
}
return this.elem[pos];
}
//返回顺序表长度
public int length(){
return this.useSize;
}
//打印顺序表
public void play(){
for(int i=0;i<this.useSize;i++){
System.out.print(this.elem[i]+"\t");
}
System.out.println();
}
//查询某个元素是否时顺序表里的
public boolean contains(int find){
for(int i=0;i<this.useSize;i++){
if(find==this.elem[i]){
return true;
}
}
return false;
}
//清空顺序表
public void clear(){
this.useSize=0;
}
综上就是实现一个顺序表基本操作的代码了，但是有一些问题：
顺序表的头部/中间的插入删除，时间复杂度为O(n)，效率有些低
增容需要扩容空间，拷贝数据，释放旧空间，会有不小的消耗
增容一般是两倍的增长，势必会有一定的空间浪费
为了解决上述问题，于是链表来了
链表
概念
链表是一种物理存储上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序决定的
无头单向非循环链表：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。
class Node1{
public Node1 next;
int val;
public Node1(int val){
this.val=val;
}
}
public class LinkList2 {
public Node1 head=null;
//头插法
public void addFirst(int val){
Node1 node=new Node1(val);
if(this.head==null){
this.head=node;
}else{
node.next=this.head;
this.head=node;
}
}
//尾插法
public void addEnd(int val){
Node1 node=new Node1(val);
if(this.head==null){
this.head=node;
}else{
Node1 cur=this.head;
while(cur.next!=null){
cur=cur.next;
}
cur.next=node;
}
}
//索引输入那个数前一个位置为head的位置
public Node1 fun(int index){
Node1 cur=this.head;
int count=0;
while(count!=index-1){
cur=cur.next;
count++;
}
return cur;
}
//中间插入法
public void addIndex(int index,int val){
if(index<0||index>length()){
System.out.println("位置非法");
return;
}
if(index==0){
addFirst(val);
return;
}
if(index==length()){
addEnd(val);
return;
}
Node1 res=fun(index);
Node1 node=new Node1(val);
node.next=res.next;
res.next=node;
}
//获取链表长度
public int length(){
int len=0;
Node1 cur=this.head;
while(cur!=null){
cur=cur.next;
len++;
}
return len;
}
//打印链表
public void display(){
Node1 cur=this.head;
while(cur!=null){
System.out.print(cur.val+"\t");
cur=cur.next;
}
System.out.println();
}
public void display1(Node1 newHead){
Node1 cur=newHead;
while(cur!=null){
System.out.print(cur.val+"\t");
cur=cur.next;
}
System.out.println();
}
//查找key值是否在链表中
public boolean contains(int key){
Node1 cur=this.head;
while(cur!=null){
if(cur.val==key){
return true;
}
cur=cur.next;
}
return false;
}
//找到删除节点的前驱
public Node1 searchPrev(int key){
Node1 cur=this.head;
while (cur.next!=null){
if(cur.next.val==key){
return cur;
}
cur=cur.next;
}
return null;
}
//删除链表节点值
public void remove(int key){
Node1 cur=this.head;
if(this.head.val==key){
this.head=this.head.next;
return;
}
Node1 prev=searchPrev(key);
if(prev==null){
System.out.println("没有这个值");
return;
}
prev.next=prev.next.next;
cur=cur.next;
}
//删除节点值为key所有节点
public Node1 allRemove(int key){
if(this.head==null){
return null;
}
Node1 cur=this.head;
Node1 curNext=this.head.next;
if(this.head.val==key){
this.head=this.head.next;
}
while(curNext!=null){
if(curNext.val==key){
cur.next=curNext.next;
curNext=curNext.next;
}else{
cur=curNext;
curNext=curNext.next;
}
}
return cur;
}
//清空表
public void clear(){
Node1 cur=this.head;
while(cur!=null){
Node1 curNext=cur.next;
cur.next=null;
cur=curNext;
}
this.head=null;
}
无头双向链表：在java集合框架中LinkedList底层实现就是无头双向循环链表
class listNode{
public int val;
public listNode next;
public listNode prev;
public listNode(int val){
this.val=val;
}
}
public class MyDoubleLinklist {
public listNode head ;//头节点
public listNode tail;//尾节点
public MyDoubleLinklist(){
listNode node = new listNode(-1);
this.head = node;
}
//头插法
public void addFirst(int val){
listNode node=new listNode(val);
if(this.head.next==null){
this.head.next=node;
node.prev=this.head;
this.tail=node;
return;
}
node.next=this.head.next;
this.head.next=node;
node.prev=this.head;
}
//尾插法
public void addEnd(int val){
listNode node=new listNode(val);
if(this.head.next==null){
this.head.next=node;
node.prev=this.head;
this.tail=node;
}else{
this.tail.next=node;
node.prev=this.tail;
this.tail=node;
}
}
//中间插入法
public void addIndex(int index,int val){
if(index<0||index>length()){
System.out.println("位置非法");
return;
}
if(index==0){
addFirst(val);
return;
}
if(index==this.length()){
addEnd(val);
return;
}
listNode cur=findIndex(index);
listNode node=new listNode(val);
cur.prev.next=node;
node.next=cur;
node.prev=cur.prev;
cur.prev=node;
}
public listNode findIndex(int index){
listNode cur=this.head.next;
int count=0;
while(count!=index){
cur=cur.next;
count++;
}
return cur;
}
//删除值为key的节点
public void delete(int key){
listNode cur=this.head.next;
while(cur!=null){
if(cur.val==key){
if(this.head.next.val==key){
this.head.next=this.head.next.next;
if(this.head.next!=null){
this.head.next.prev=null;
}else{
this.tail=null;
}
}else{
if(cur.next!=null){
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}else{
cur.prev.next=cur.next;
tail=cur.prev;
}
}
}
cur=cur.next;
}
}
//删除双向链表值为key的所有节点
public void deleteAllKey(int key) {
listNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
if (this.head.next.val == key) {
this.head.next = this.head.next.next;
if (this.head.next != null) {
this.head.next.prev = null;
} else {
this.tail = null;
}
} else {
if (cur.next != null) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
} else {
cur.prev.next = cur.next;
tail = cur.prev;
}
}
}
cur = cur.next;
}
}
//查找key是否在双向练表里
public boolean contains(int key){
listNode cur=this.head.next;
while(cur!=null){
if(cur.val==key){
return true;
}
cur=cur.next;
}
return false;
}
//打印链表
public void display(){
listNode cur=this.head.next;
while(cur!=null){
System.out.print(cur.val+"\t");
cur=cur.next;
}
System.out.println();
}
//计算双向链表长度
public int length(){
listNode cur=this.head.next;
int count=0;
while(cur!=null){
cur=cur.next;
count++;
}
return count;
}
//清除双向链表
public void clear(){
listNode cur=this.head.next;
while(cur!=null){
listNode curNext=cur.next;
cur.next=null;
cur.prev=null;
cur=curNext;
}
this.head.next=null;
this.tail=null;
}
}
总结：
顺序表和链表的区别和联系
顺序表：优点：空间连续，支持随机访问
缺点：中间或前面插入删除时间复杂度为O(n),扩容代价较大
链表：优点：任意位置的插入删除时间复杂度为O(1),没有扩容问题，插入一个开辟一个空间
缺点：以节点为单位存储，不支持随机访问