• Iterable、Collection、List等接口

    文章目录

    前言

    本篇文章总结了常用的接口list、queue、set、map等之间的关系以及使用方法。

    一、接口的关系

    图中的都是一些接口，按照箭头的方向为子类指向父类接口，使用他们则需要使用具体的实现类，list下常用的类有Stack、ArrayList、LinkedList；queue常用的类有LinkedList、PriorityQueue；Set常用用的类有TreeSet、HashSet;Map常用的类有TreeMap、HashMap。
    在这里插入图片描述
    ArrayList的底层实现是顺序表，其在物理和逻辑上都是连续存储的，LinkedList的底层实现是链表，其逻辑上是连续的但实际不是连续的存储单元，ArrayList相较LinkedList而言在查找上更迅速，而单链表更适合运用在数据大量的增删操作上。

    二、使用方法

    1.ArrayList

    ArrayList的底层是一个数组。

    public class MyArraylist {
    public int[] elem;
    public int usedSize;
    private static final int DEFAULT_SIZE = 10;
    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }
    /**
     * 打印顺序表:
     *   根据usedSize判断即可
     */
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if(isFull()) {
            System.out.println("扩容");
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        elem[this.usedSize++] = data;
    }

    /**
     * 判断当前的顺序表是不是满的！
     * @return true:满   false代表空
     */
    public boolean isFull() {
        if(this.usedSize == elem.length) {
            return true;
        }
        return false;
    }


    private boolean checkPosInAdd(int pos) {
        if(pos<0||pos>=this.usedSize) {
            return false;
        }
        return true;//合法
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if(checkPosInAdd(pos)) {
            for(int i=this.usedSize-1;i>=pos;i--) {
                this.elem[i+1] = this.elem[i];
            }
            this.elem[pos] = data;
            this.usedSize++;
        }else {
            System.out.println("pos位置不合法");
        }
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        if(indexOf(toFind)>=0) {
            return true;
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(elem[i]==toFind) {
                return i;
            }
        }
        return -1;
    }

    // 获取 pos 位置的元素
    public int get(int pos) {
        if(checkPosInAdd(pos)) {
            return this.elem[pos];
        }
        return -1;
    }

    private boolean isEmpty() {
        if(this.usedSize==0) {
            return true;
        }
        return false;
    }
    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        if(checkPosInAdd(pos)) {
            this.elem[pos] = value;
        }else {
            System.out.println("pos位置不合法");
        }
    }

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        int index = indexOf(key);
        if(index<0) {
            System.out.println(key+"不存在！");
            return;
        }
        for (int i = index; i < this.usedSize; i++) {
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
    }

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

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126

    2.LinkedList

    双向链表比起单链表更加的方便，双向链表的每一个结点有前驱和后继，删除结点的时候需要将其置null。
    LinkedList：

    public class MyLinkedList {
    class LinkNode {
        public int val;
        public LinkNode next;
        public LinkNode pre;

        public LinkNode(int val) {
            this.val = val;
        }
    }
    public LinkNode head;
    public LinkNode last;
    //头插法
    public void addFirst(int data) {
        LinkNode node = new LinkNode(data);
        if (head == null) {
            head = node;
            last = node;
        }else {
            node.next = head;
            head.pre = node;
            head = node;
        }
    }
    //尾插法
    public void addLast(int data) {
        LinkNode node = new LinkNode(data);
        if(head == null) {
            head = node;
            last = node;
        }else {
            node.pre = last;
            last.next = node;
            last = node;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        if(index<0||index>=size()) return;
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()-1) {
            addLast(data);
            return;
        }
        LinkNode node = new LinkNode(data);
        LinkNode cur = head;
        while (index != 1) {
            cur = cur.next;
            index--;
        }
        node.next = cur.next;
        node.pre = cur;
        cur.next.pre = node;
        cur.next = node;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        LinkNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if(head == null) return;
        if(head.val == key) {
            head = head.next;
            return;
        }
        LinkNode cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(head == null) return;
        LinkNode cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
        }
    }
    //得到单链表的长度
    public int size() {
        int count = 0;
        LinkNode cur = head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    public void display() {
        LinkNode cur = head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear() {
        LinkNode cur = head;
        while (cur != null) {
            LinkNode curNext = cur.next;
            cur.next = null;
            cur.pre = null;
            cur = curNext;
        }
        head = null;
        last = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130

    3.Stack

    栈的规则是先进后出，可以使用两个队列来实现栈。
    1.入栈的时候入到空队里面；
    2.出栈的时候出size-1个元素到空栈里面，剩余一个元素则就是需要出队的元素。

    class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;


    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(!empty()) {
            if(!q1.isEmpty()) {
                q1.offer(x);
            }else{
                q2.offer(x);
            }
        }else{
            q1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(!q1.isEmpty()) {
            int size = q1.size();
            for(int i=0;i<size-1;i++) {
                q2.offer(q1.poll());
            }
            return q1.poll();
        }else{
            int size = q2.size();
            for(int i=0;i<size-1;i++) {
                q1.offer(q2.poll());
            }
            return q2.poll();
        }
    }
    
    public int top() {
        if(empty()) {
            return -1;
        }
        if(!q1.isEmpty()) {
            int size = q1.size();
            int tmp = -1;
            for(int i=0;i<size;i++) {
                tmp=q1.poll();
                q2.offer(tmp);
            }
            return tmp;
        }else{
            int size = q2.size();
            int tmp = -1;
            for(int i=0;i<size;i++) {
                tmp=q2.poll();
                q1.offer(tmp);
            }
            return tmp;
        }
    }
    
    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    4.Queue

    队列遵循先进先出的规则，可以使用两个栈实现队列，一个栈用来作为入队，另一个栈用来作为出栈。

    class MyQueue {
    Stack<Integer> s1;//入队
    Stack<Integer> s2;//出队


    public MyQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(!s2.empty()) {
            return s2.pop();
        }else{
            int size=s1.size();
            for(int i=0;i<size;i++) {
                s2.push(s1.pop());
            }
            return s2.pop();
        }
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(!s2.empty()) {
            return s2.peek();
        }else{
            int size=s1.size();
            for(int i=0;i<size;i++) {
                s2.push(s1.pop());
            }
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.empty()&&s2.empty();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    5.PriorityQueue

    优先级队列创建出来的是一个大根堆或小根堆，大根堆还是小根堆主要看比较器，对于自定义类型必须传入比较器。

    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    寻找最小k个数：

        public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr.length == 0 || k <= 0) return ret;
        //1.创建大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //2.创建k个值的大根堆
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //3.将较小的值放入大根堆
        for (int i = k; i < arr.length; i++) {
            if(arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        //4.将前k个最小值放入数组
        for (int i = ret.length - 1; i >= 0; i--) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
  • 相关阅读:
    《论文阅读》同情对话生成的知识桥梁 AAAI 2021
    语义分割 语义通信 增强模型图片处理
    说一下JVM类加载机制？
    源码构建Tomcat 8.5.81启动
    【Pygame实战】打扑克牌嘛？赢了输了？这款打牌游戏，竟让我废寝忘食。
    《每天5分钟用Flask搭建一个管理系统》第11章：测试与部署
    WPF随笔收录-实时绘制心率曲线
    一周学会Django5 Python Web开发-Django5列表视图ListView
    DASCTF X GFCTF 2022十月挑战赛
    FPGA面试笔试一些基础概念题目
  • 原文地址：https://blog.csdn.net/qq_45283185/article/details/125950067