[数据结构与算法]JavaSE数据结构之顺序表和链表

JavaSE数据结构之顺序表和链表

顺序表🌜

• 用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下使用数组存储，在数组上完成数据的增删查改。如顺序表的一个类：

class MyArrayList{
    public int[] elem;
    public int usedSize;
    
    public myarraylist(){
        this.elem=new int[10];
    }  
}

• 当在主测试函数中用MyArrayList去实例化对象时的底层存储：（插入一个图片）
• 实现顺序表的增删查改等功能函数

class MyArrayList{
    public int[] elem;
    public int usedSize;
    
    public myarraylist(){
        this.elem=new int[10];
    }
    //打印顺序表
    public void display(){
        for(int i=0;i<this.usedSize;i++){
            System.out.print(elem[i]+" ")
        }
        System.out.println;//打印结束进行换行
    }
    //获取顺序表长度
    public int size(){
        return this.usedSize;
    }
    //在index（下标）位置新增元素
    public boolean isFull(){
        return elem.length==this.usedSize;
    }
    public void addIndex(int index,int data){
        if(index<0||index>this.usedSize){
            system.out.println("下标位置不合法");
            return;
        }
        if(isFull){
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }//扩容
        for(int i=usedSize-1;i>=index;i--){
            this.elem[i+1]=this.elem[i];
        }
        this.elem[index]=data;
        this.usedSize++;//容易忘
    }
    //判定顺序表中是否包含某关键字key
    public boolean contains(int key){
        for(int i=0;i<usedSize;i++){
            if(this.elem[i]==key){
                return true;
            }
        }
        return false;
    }
    //查找某个元素的位置
    public int search(int toFind){
        for(int i=0;i<this.usedSize;i++){
            if(this.elem[i]==toFind){
                return i;
            }
        }
        return -1;
    }
    //获取pos位置处的元素
    public boolean isEmpty(){
        return this.usedSize==0;
    }
    public int getPos(int pos){
        if(pos<0||pos>this.usedSize-1){
            System.out.println("pos位置不合法");
            return -1;
        }
        if(isEmpty()){
            System.out.println("顺序表为空");
            return -1;
        }
        return this.elem[pos];
    }
    //给pos位置设置成value
    public void setPos(int pos,int value){
        if(pos<0||pos>this.usedSize-1){
            System.out.println("位置不合法");
            return;
        }
        if(isEmpty()){
            System.out.println("顺序表为空");
            return;
        }
        this.elem[pos]=value;
    }
    //删除第一次出现关键字key的“节点”
    public void remove(int key){
        if(isEmpty()){
            System.out.println("顺序表为空")
                return;
        }
        int index=search(key);
        if(index==-1){
            System.out.println("查无此数");
            return;
        }
        for(int i=index;i<this.usedSize-1;i++){
            this.elem[i]=this.elem[i+1];
        }
        this.usedSize--;
    }
    //清空顺序表
    public void clear(){
        this.usedSize=0;
    }
}

• 顺序表的缺点
  1. 插入和删除元素需要移动元素→时间复杂度为O（N）；
  2. 扩容也是个问题，如上述代码每次开辟10个位置，所以很大可能不会充分利用起开辟的空间，资源浪费。

链表🦄

• 逻辑上连续物理上不一定连续的一种数据存储结构
• 重点研究单向不带头非循环链表、双向不带头非循环链表（根据是否单向、是否带头、是否循环可以有2^3=8种链表）
• 每个节点应有数据域和指针域两块

class ListNode{
    public int val;//数据域
    public ListNode next;//指针域
    
    public ListNode(int value){
        this.val=value;//构造初始化
    }
}

• 什么是带头不带头？

  带头意思就是说：不管你链表怎么新增或者删除节点，我的头节点的指针总是存在一个固定的“傀儡节点”中；不带头的意思：每头插一个元素，链表的头节点都会更新为这个新节点，此时并没有傀儡节点去存该节点的指针。

• 什么叫循环非循环？

  循环的意思是：尾巴节点的next存的是头节点的指针（此时构成了一个大环）；非循环的意思就是没有首尾相连。

• 什么是双向？

  上述的代码是单向的利用next往后一个个节点去走，双向的意思就是每个节点多一个域，这个域存的是上一个节点的指针，即prev

• 实现简单链表

class ListNode{
    public int val;
    public ListNode next;
    
    public ListNode(int value){
        this.val=value;
    }
}
public class MyLinkedList{
    ListNode head;//设头
    
    public void create(){
        //简单的可穷举节点的情况
        ListNode listNode1=new ListNode(11);
        ListNode listNode2=new ListNode(22);
        ListNode listNode3=new ListNode(33);
        ListNode listNode4=new ListNode(44);
        ListNode listNode5=new ListNode(55);
        
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;//listNode5.next=null;是默认的
        
        this.head=listNode1;//定头       
    }
    //打印链表
    public void display(){
        ListNode cur=this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();//打印完换行
    }
    //查找关键字key是否在链表中
    public boolean contains(int key){
        if(this.head==null){
            return null;
        }
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //得到单链表的长度
    public int size(){
        int count=0;
        ListNode cur=this.head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //头插
    public void addFirst(int data){
        ListNode node=new ListNode(data);
        node.next=this.head;
        this.head=node;
    }
    //尾插
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(this.head==null){
            head=node;
            return;
        }
        ListNode cur=this.head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }
    //任意位置插入节点
    public ListNode findIndex(int index){
        ListNode cur=this.head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;//找到下述代码的前驱节点
    }
    public void addIndex(int index,int data){
        if(index<0||index>size()){
            System.out.println("下标不合法");
            return;
        }
        ListNode node = new ListNode(data);
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        //介于头尾的去插
        ListNode cur=findIndex(index);//已保证下标index合理
        node.next=cur.next;
        cur.next=node;  
    }
    //删除第一次出现关键字key的节点（找前驱再跳过它就可以）
    public ListNode searchPre(int key){
        ListNode cur=this.head;
        while(cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    public void remove(int key){
        if(this.head==null){
            System.out.println("链表为空");
            return;
        }
        //因为头结点没有前驱，所以考虑一下头结点的情况
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
        ListNode prev=searchPre(key);
        if(prev==null){
            System.out.println("查无此数");
            return;
        }
        prev.next=prev.next.next;
    }
    //删除所有包含关键字key的节点
    public void removeAll(int key){
        if(this.head==null){
            System.out.println("链表为空");
            return;
        }
        //先不考虑头结点
        ListNode prev=this.head;
        ListNode cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        //处理刚才的头
        if(this.head.val==key){
            this.head=this.head.next;
        }
        return this.head;
    }
    //清空链表：暴力解法就是this.head=null;就可以了，这里说一下逐一回收
    public void clear(){
        while(this.head!=null){
            ListNode curNext=this.head.next;
            this.head.next=null;
            this.head=curNext;
        }
    }
}

• 刷链表题即可（力扣、牛客）