数据结构入门，先从顺序表，链表开始

• 线性表
• • 顺序表
  • 链表

线性表

线性表（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),没有扩容问题，插入一个开辟一个空间
缺点：以节点为单位存储，不支持随机访问