顺序表和链表

作者：~小明学编程 

文章专栏：Java数据结构

格言：目之所及皆为回忆，心之所想皆为过往

目录

顺序表

概念和结构

实现顺序表

接口实现

打印顺序表

判断顺序表是否已满

判断顺序表是否为空

获取顺序表的长度

在指定位置添加元素

判断是否包含某个元素

获取pos位置的元素

给 pos 位置的元素设为 value

 删除第一次出现的关键字key

清空顺序表

完整的顺序表以及功能方法

功能演示

顺序表的问题及思考

链表

链表的概念及结构

 链表的实现（无头单项非循环链表）

链表的单位结构

创建链表

打印链表

插入元素（头插法）

插入元素（尾插法）

插入元素（任意位置插入）

查找是否包含关键字key是否在单链表当中

删除第一次出现关键字为key的节点

得到单链表的长度

清空链表

顺序表

概念和结构

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

   public void disPlay() {
        for (int i = 0; i < numSize; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }

 //判断顺序表是否是满的
    public boolean isFull() {
        if(this.elem.length==this.numSize) {
            return true;
        }else {
            return false;
        }
    }

//判断顺序表是否为空
    public boolean isEmpty(){
 
        return numSize==0;
    }

 //获取顺序表长度
    public int size(){
        
        return this.numSize;
    }

//在pos位置增加一个元素
    public void add(int pos,int data) {
        if (pos<0||pos>numSize){
            System.out.println("您添加的位置不合法！");
        }else {
            if(isFull()){//元素已满进行扩容
                this.elem = Arrays.copyOf(this.elem,this.elem.length+2);
            }
            for (int i = numSize-1; i >= pos ; i--) {
                this.elem[i+1] = this.elem[i];
            }
            this.elem[pos] = data;
            this.numSize++;
        }
    }

//判断是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < numSize; i++) {
            if(this.elem[i]==toFind) {
                return true;
            }
        }
        return false;
    }

   // 获取 pos 位置的元素
    public int getPos(int pos){
        if(pos<0||pos>numSize){
            return -1;
        }
        if(isEmpty()){
            return -1;
        }
        return this.elem[pos];
    }

 // 给 pos 位置的元素设为 value
    public void setPos(int pos, int value){
        if(pos<0||pos>numSize){
            System.out.println("pos位置不合法！");
        }
        if(isEmpty()){
            System.out.println("顺序表为空！");
        }
        this.elem[pos] = value;
    }

//删除第一次出现的关键字key
    public void remove(int toRemove) {
        if(getPos(toRemove)==-1){
            System.out.println("要删除的元素不存在");
        }else {
            for (int i = getPos(toRemove); i < numSize-1; i++) {
                this.elem[i] = this.elem[i+1];
            }
            numSize--;
        }
    }

//清空顺序表
    public void clear(){
        numSize = 0;
    }

    //打印顺序表
    public void disPlay() {
        for (int i = 0; i < numSize; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }
    //在pos位置增加一个元素
    public void add(int pos,int data) {
        if (pos<0||pos>numSize){
            System.out.println("您添加的位置不合法！");
        }else {
            if(isFull()){//元素已满进行扩容
                this.elem = Arrays.copyOf(this.elem,this.elem.length+2);
            }
            for (int i = numSize-1; i >= pos ; i--) {
                this.elem[i+1] = this.elem[i];
            }
            this.elem[pos] = data;
            this.numSize++;
        }
    }
    //判断顺序表是否是满的
    public boolean isFull() {
        if(this.elem.length==this.numSize) {
            return true;
        }else {
            return false;
        }
    }
    //判断是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < numSize; i++) {
            if(this.elem[i]==toFind) {
                return true;
            }
        }
        return false;
    }
    // 获取 pos 位置的元素
    public int getPos(int pos){
        if(pos<0||pos>numSize){
            return -1;
        }
        if(isEmpty()){
            return -1;
        }
        return this.elem[pos];
    }
    //判断顺序表是否为空
    public boolean isEmpty(){
        return numSize==0;
    }
    // 给 pos 位置的元素设为 value
    public void setPos(int pos, int value){
        if(pos<0||pos>numSize){
            System.out.println("pos位置不合法！");
        }
        if(isEmpty()){
            System.out.println("顺序表为空！");
        }
        this.elem[pos] = value;
    }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        if(getPos(toRemove)==-1){
            System.out.println("要删除的元素不存在");
        }else {
            for (int i = getPos(toRemove); i < numSize-1; i++) {
                this.elem[i] = this.elem[i+1];
            }
            numSize--;
        }
    }
    //获取顺序表长度
    public int size(){
        return this.numSize;
    }
    //清空顺序表
    public void clear(){
        numSize = 0;
    }

功能演示

前面我们已经将我们的类以及里面的方法全部写好了，接下来我们就可以测试一下我们的顺序表是否可以使用了。

public class Dome {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        for (int i = 0; i < 20; i++) {
            myArrayList.add(i,i);
        }
        myArrayList.add(15,99);
        myArrayList.disPlay();
        myArrayList.setPos(5,88);
        myArrayList.disPlay();
        System.out.println(myArrayList.contains(14));
        System.out.println(myArrayList.getPos(16));
        myArrayList.remove(10);
        myArrayList.disPlay();
        myArrayList.remove(100);
        myArrayList.clear();
        myArrayList.disPlay();
    }
}

顺序表的问题及思考

1. 顺序表中间 / 头部的插入删除，时间复杂度为 O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到 200 ，我们再继 续插入了5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。

链表

链表的概念及结构

实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

单向、双向

带头、不带头

循环、非循环

 

 

虽然有这么多的链表的结构，但是我们重点掌握两种 :

无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ，如哈希桶、图的邻接表等等。另外这种结构在笔试面试 中出现很多。

 链表的实现（无头单项非循环链表）

链表的单位结构

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

这就是组成我们链表的结构我们把它封装成一个类，类里面有存放我们数据的val,还有存放下一个节点的指针next,最后我们再存放一个构造方法方便我们存放数据。

创建链表

public class MyLinkedList {
        public ListNode head;
        public void createList() {
            ListNode listNode1 = new ListNode(1);
            ListNode listNode2 = new ListNode(100);
            ListNode listNode3 = new ListNode(32);
            ListNode listNode4 = new ListNode(42);
            ListNode listNode5 = new ListNode(52);
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
            listNode4.next = listNode5;
            this.head = listNode1;
 
        }
}

我们这里再次封装一个大类里面放着我们对链表的各种操作，其中我们首先介绍一下我们创建链表的方法，这里说明一下最开始的引用变量head，head是用来存放我们第一个节点的地址的。

接着我们通过创建对象的方法来创建出我们的单位链表，然后再将它们链接起来就组成了我们的链表。

打印链表

//打印所有节点里面的值
        public void display() {
            ListNode cur = this.head;
            while(cur!=null) {
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }

我们首先定义一个首节点的引用，然后遍历我们整个链表，如果我们的cur所引用的对象的地址是一个空地址就代表着，遍历到了我们的最后一个元素了，至此打印结束。

插入元素（头插法）

//头插法
        public void addFirst(int data) {
            ListNode node = new ListNode(data);
            node.next = head;
            head = node;
 
        }

我们先new一个新的对象用于存放我们的新元素，然后将我们新对象的所指向的下一个节点改为指向原来的head也就是首节点，最后我们再将我们的首节点指向我们的新对象。

插入元素（尾插法）

    //尾插法
        public void addLast(int data) {
            ListNode node = new ListNode(data);
            ListNode cur = this.head;
            if(cur==null) {
                head = node;
            } else {
                while(cur.next!=null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
 
        }

首先，我们要new一个对象并且复制一个首元素进行操作，然后分两种情况讨论，一种就是空链表，另外就是非空，当我们的链表是空的时候我们直接将首节点改为node就行了，当非空时通过一个循环找到最后一个元素，然后将最后一个元素的指针改为我们的node就行了。

插入元素（任意位置插入）

//任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data) {
            ListNode node = new ListNode(data);
            ListNode cur = this.head;
            //插入位置是0时直接头插
            if(index==0) {
                addFirst(data);
                return;
            }
            //插入位置是最后的时候直接是尾插
            if (index==size()) {
                addLast(data);
                return;
            }
            while(index-1!=0&&cur!=null) {
                cur = cur.next;
                index--;
            }
            if (cur==null){
                System.out.println("插入位置不合法！");
                return;
            }
            node.next = cur.next;
            cur.next = node;
        }

首先，我们要new一个对象并且复制一个首元素进行操作，因为我们要实现从任意位置插入的方法，所以我们插入的方式就可能有三种情况，分别是头插，尾插，还有中间插入，前面两种情况我们前面已经实现了，只需要判断一下相应的情况然后调用该方法就可以了，对于从中间插入的情况我们再做分析，首先就是要判断插入位置的合理性index下标过大或者过小的话都会导致我们的cur最后指向null进而告诉我们插入位置不合理，当满足我们的插入条件后我们就可以进行插入操作了。

 我们新节点node的next是我们插入节点的下一个节点的地址，也就是对应我们的

node.next = cur.next;

然后插入位置的的cur的next则是我们插入元素的地址，也就是

cur.next = node;

查找是否包含关键字key是否在单链表当中

//查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
            ListNode cur = this.head;
            while(cur!=null) {
                if(cur.val==key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

这个太简单了不解释。

删除第一次出现关键字为key的节点

//删除第一次出现关键字为key的节点
        public void remove(int key) {
            if(this.head==null) {
                System.out.println("该链表为空！");
            }else {
                ListNode cur = this.head;
                if (cur.val==key) {
                    this.head = cur.next;
                }else {
                    while(cur.next!=null){
                        if(cur.next.val==key){
                            cur.next = cur.next.next;
                            break;
                        }
                        cur = cur.next;
                        if (cur.next==null) {
                            System.out.println("没找到要删除的结点！");
                        }
                    }
                }
 
            }
 
        }

首先还是判断链表是否为空和复制一下我们的首节点，接着判断一下我们的首节点是不是我们要删除的节点是的话我们的首节点就直接指向我们的下一个节点，不是的话我们就通过循环找到我们的key，因为我们找到的是cur.next.val==key也就是我们目标的上一个节点，所以我们就将上一个节点，直接指向我们的下一个节点就可以了，没找到key的话就最终指向null,然后输出相关的语句。

//删除所有值为key的节点
        public ListNode removeAllKey(int key) {
            if(this.head==null) {
                System.out.println("该链表为空！");
                return null;
            }else {
                ListNode cur = this.head.next;
                ListNode prev = this.head;
                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;
 
            }
 
        }

这里我们复制两个节点一个是我们的首节点prev当作我们的前驱节点，还有一个就是cur是我们的第二个节点也就是我们当前搜索的节点。

如果我们的cur中的值为key那么我们的前驱节点直接指向我们cur的下个节点的地址,如果不是key,则我们的前驱节点等于我们当前的cur,cur接着向下指。最后我们再判断一下我们首节点的特殊情况，如果我们的首节点就是key的话，那么我们的首节点就是我们首节点指向的下一个节点。

得到单链表的长度

 //得到单链表的长度
        public int size() {
            int size = 0;
            ListNode cur = this.head;
            while(cur!=null) {
                size++;
                cur = cur.next;
            }
            return size;
        }

清空链表

//清空链表
        public void clear() {
            this.head=null;
        }