devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

图灵之旅--ArrayList&顺序表&LinkedList&链表&&栈&&Stack&&队列&&Queue

作者：我家自动化 | 2024-04-15 10:11:43

赞

踩

图灵之旅--ArrayList&顺序表&LinkedList&链表&&栈&&Stack&&队列&&Queue

目录

线性表

线性表是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛应用的数据结构
线性表在逻辑层面是连续的,但在物理结构上不一定连续,线性表在物理结构中存储一般以数组或者链式结构的形式存在

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下是以数组来进行存储数据.在数组中进行增删改查
接口实现


public class List implements MyArrayList{

    private int[] elements;
    private int usedSize;
    //顺序表的默认大小
    private static final int DEFAULT_SIZE = 2;

    public List() {
        this.elements = new int[DEFAULT_SIZE];
    }
    public List(int capacity) {
        this.elements = new int[capacity];
    }

    @Override
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elements[i]+" ");
        }
        System.out.println();
    }

    @Override
    public boolean isFull() {
        /*if(this.usedSize==this.elements.length) {
            return true;
        }
        return false;*/
        return this.elements.length==usedSize;
    }
    private void isEnlarger() {
        if(isFull()) {
            elements = Arrays.copyOf(elements,elements.length*2);
        }
    }
    @Override
    public void add(int data) {
        isEnlarger();
        this.elements[this.usedSize] = data;
        this.usedSize++;
    }

    @Override
    public void add(int pos, int data) {
        try {
            checkPos(pos);
        } catch (PosIllegal e) {
            e.printStackTrace();
            return;
        }
        isEnlarger();
        int move = usedSize;
        while (move-1>=pos) {
            elements[move] = elements[move-1];
            move--;
        }
        elements[pos] = data;
        usedSize++;
    }


    private void checkPos(int pos) throws PosIllegal{
        if(pos<0||pos>usedSize) {
            throw new PosIllegal("插入下标异常: "+pos);
        }
    }

    @Override
    public boolean contains(int toFind) {
        if(isEmpty()) {
            return false;
        }
        for (int i = 0; i < usedSize; i++) {
            //查找引用类型,要重写方法
            if(toFind==elements[i]) {
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean isEmpty() {
        return usedSize==0;
    }

    @Override
    public int indexOf(int toFind) {
        if(isEmpty()) {
            return -1;
        }
        for (int i = 0; i < usedSize; i++) {
            //查找引用类型,要重写方法
            if(toFind==elements[i]) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int get(int pos) {
        try {
            checkPosOnGet(pos);
        } catch (PosIllegal e) {
            e.printStackTrace();
        }

        return elements[pos];
    }
    private void checkPosOnGet(int pos) throws PosIllegal{
        if(pos<0||pos>=usedSize) {
            throw new PosIllegal("获取指定下标异常: "+pos);
        }
    }

    @Override
    public void set(int pos, int value) {
        try {
            checkPosOnGet(pos);
        } catch (PosIllegal e) {
            e.printStackTrace();
            return;
        }
        elements[pos] = value;
    }

    @Override
    public void remove(int toRemove) {
        if(indexOf(toRemove)==-1) {
            System.out.println("无该数值可以删除");
            return;
        }
        int i = indexOf(toRemove);
        while (i+1< usedSize) {
            elements[i] = elements[i+1];
            i++;
        }

        usedSize--;
    }
    @Override
    public int size() {
        return usedSize;
    }

    @Override
    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
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154

ArrayList简介

在集合框架里,ArrayList是一个普通的类,实现List接口
说明

  1. ArrayList是以泛型方式实现的,使用时必须要先实例化
  2. ArrayList实现了RandomAccess接口,表明ArrayList支持随机访问
  3. ArrayList实现Cloneable接口,表明ArrayList是可以clone的
  4. ArrayList实现了Serializable,表明ArrayList是支持序列化的
  5. ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表

ArrayList使用

ArrayList的构造

方法
ArrayList() 无参构造
ArrayList(Collection<? extends E> c) 利用其他Collection构建ArrayList
ArrayList(int initialCapacity) 指定顺序表初识容量

在这里插入图片描述
Collection<? extends E>中?是通配符
将来给ArrayList可以传入Collection

//类型是ArrayList,ArrayList实现了Collection接口,类型匹配
        ArrayList<Integer> arrayList = new ArrayList<>();
//你当前传入的arraylist里面的元素一定是ArrayList<Integer> arrayList1中Integer的子类
        ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);

  • 1
  • 2
  • 3
  • 4

换个栗子

        ArrayList<Integer> arrayList = new ArrayList<>();
//Integer是Number的子类
        ArrayList<Number> arrayList1 = new ArrayList<>(arrayList);

  • 1
  • 2
  • 3

在这里插入图片描述
Collection<? extends E>中?是E的子类或者E本身
传入的arrayList一定是Number或者Number的子类,结合如下代码,E和?的代表分别是Number和Integer
在这里插入图片描述
这种构造方法可以将集合一组内容都填充到另一个List里面,类似应用如下代码:

    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(1);

        ArrayList<Number> arrayList1 = new ArrayList<>(arrayList);
        arrayList1.add(2);
        arrayList1.add(2);
        arrayList1.add(2);
        System.out.println(arrayList1);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

在这里插入图片描述

ArrayList常见操作

boolean addAll(Collection<? extends E> c) 尾插 c 中的元素

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(1);
        ArrayList<Number> list1 = new ArrayList<>();
        list1.addAll(list);
        System.out.println(list1);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

在这里插入图片描述

E remove(int index) 删除 index 位置元素

boolean remove(Object o) 删除遇到的第一个 o

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.remove(new Integer(4));
        System.out.println(list);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述
E get(int index) 获取下标 index 位置元素

E set(int index, E element) 将下标 index 位置元素设置为 element

void clear() 清空

boolean contains(Object o) 判断 o 是否在线性表中

int indexOf(Object o) 返回第一个 o 所在下标

int lastIndexOf(Object o) 返回最后一个 o 的下标

List subList(int fromIndex, int toIndex) 截取部分 list

ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器
for循环+下标

        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(1);

        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

foreach

        for (Integer x : list) {
            System.out.print(x+" ");
        }

  • 1
  • 2
  • 3

迭代器(使用迭代器遍历集合类)

        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(1);

        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next()+" ");
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

ArrayList最长使用的遍历方式是:for循环+下标以及foreach

ArrayList的扩容机制

ArrayList是一个动态类型的顺序表,就是在插入元素的时候会自动扩容
检测是否真正需要扩容,如果是调用grow准备扩容
预计需要扩容的大小

  1. 初步预估扩容1.5倍
  2. 如果用户所需大小超过预估1.5倍,则按照用户所需大小进行扩容
  3. 真正扩容之前检测是否能扩容成功,防止太大导致扩容失败
    使用copyOf进行扩容

利用ArrayList洗牌

卡包

package card;

public class Card {
    private String color;//花色
    private int number;//数字

    public String getColor() {
        return color;
    }

    public Card(String color, int number) {
        this.color = color;
        this.number = number;
    }

    public void setColor(String color) {
        this.color = color;
    }

    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    @Override
    public String toString() {
        return color+":"+number;
    }
}


  • 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

操作包

package card;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class CardDemo {
    private String[] suits = {"♥","♠","♦","♣"};
    public List<Card> buyCard() {
        List<Card> list = new ArrayList<>();
        //创建一副新牌
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                Card card = new Card(suits[i], j);
                list.add(card);
            }
        }
        return list;
    }
    public void dislocate(List<Card> cardList) {
        Random random = new Random();
        //从后往前开始进行互换,打乱牌面
        for (int i = cardList.size()-1; i > 0 ; i--) {
            int rand = random.nextInt(i);
            swap(cardList,i,rand);
        }

    }
    public static void swap(List<Card> cardList,int x,int y) {
    //交换牌
        Card tmp = cardList.get(x);
        cardList.set(x,cardList.get(y));
        cardList.set(y,tmp);
    }
    public void Inauguration(List<Card> cardList) {
        List<List<Card>> roles = new ArrayList<>();
        //三个人的牌建立顺序表储存
        List<Card> role1 = new ArrayList<>();
        List<Card> role2 = new ArrayList<>();
        List<Card> role3 = new ArrayList<>();
        roles.add(role1);
        roles.add(role2);
        roles.add(role3);
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
            //摸牌
                Card card = cardList.get(0);
                roles.get(j).add(card);
                cardList.remove(0);
            }
        }
        System.out.println("第一个人的牌");
        System.out.println(roles.get(0));
        System.out.println("第二个人的牌");
        System.out.println(roles.get(1));
        System.out.println("第三个人的牌");
        System.out.println(roles.get(2));

        System.out.println("剩余的牌");
        System.out.println(cardList);
    }
}


  • 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

测试包

package card;

import java.util.List;

public class Test {
    public static void main(String[] args) {
        CardDemo cardDemo =  new CardDemo();
        List<Card> cardList = cardDemo.buyCard();
        System.out.println("扑克牌如下 : ");

        System.out.println(cardList);

        System.out.println("打乱如下");
        cardDemo.dislocate(cardList);
        System.out.println(cardList);

        cardDemo.Inauguration(cardList);
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

ArrayList的优缺点

缺点

  1. 插入数据必须移动其他数据,最坏情况插入0位置,时间复杂度O(N)
  2. 删除数据也要移动数据,最坏情况删除0位置,时间复杂度O(N)
  3. 扩容之后有可能会浪费空间

优点
4. 在给定下标进行查找的时候,时间复杂度O(1)

总结
顺序表比较适合给定下标查找的场景

链表

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用来进行链接的

链表的实现

链表接口

package Demo01;

public interface Ilist {
//头插法
        void addFirst(int data);
//尾插法
        void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
        void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
        boolean contains(int key);
//删除第一次出现关键字为key的节点
        public void remove(int key);
//删除所有值为key的节点
        void removeAllKey(int key);
//得到单链表的长度
        int size();
        void clear();

        void display();
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

链表实现

package Demo01;

import org.omg.CORBA.CODESET_INCOMPATIBLE;

import java.util.List;

public class MyList implements Ilist{
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    @Override
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        head = newNode;
    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        if(head==null) {
            head = newNode;
        } else {
            ListNode curNode = head;
            while (curNode.next!=null) {
                curNode = curNode.next;
            }
            curNode.next = newNode;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        ListNode newNode = new ListNode(data);
        if(index<0||index>size()) {
            System.out.println("插入下标违法");
            return;
        }
        if(index==0) {
            addFirst(data);
        } else {
            int count = 0;
            ListNode curNode = head;
            while(count+1!=index) {
                curNode = curNode.next;
                count++;
            }
            ListNode tmp = curNode.next;
            curNode.next = newNode;
            newNode.next = tmp;
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur!=null) {
            if(cur.val==key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head==null) {
            return;
        }
        if(!contains(key)) {
            System.out.println("不存在该值");
            return;
        }
        if(head.val==key) {
            head = head.next;
        } else {
            ListNode curNode = head;
            while (curNode.next.val!=key) {
                curNode = curNode.next;
            }
            curNode.next = curNode.next.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        if(head==null) {
            return;
        }
        if(!contains(key)) {
            System.out.println("该值不存在,无法删除");
            return;
        }
        while (head!=null&&head.val==key) {
            head = head.next;
        }
        if(head!=null) {
            ListNode curNode = head;
            while (curNode.next !=null) {
                if (curNode.next.val==key) {
                    curNode.next = curNode.next.next;
                } else {
                    curNode = curNode.next;
                }
            }
        }
    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;

        while (cur!=null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {

        if(head!=null) {
            while (head!=null) {
                ListNode tmp = head.next;
                head = null;
                head = tmp;
            }
        }
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur!=null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}


  • 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
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149

双向链表的实现

双向链表的实现


public class MyLinkedList implements Ilist{
//双向链表的节点
    static class ListNode {
    	//后继
        public ListNode next;
        //前驱
        public ListNode prev;
        public int val;
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
    public ListNode last;
    //头插法
    @Override
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        if(head!=null) {
            head.prev = newNode;
            newNode.next = head;
            head = newNode;
        } else {
            head = last = newNode;
        }
    }
	//尾插法
    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        if(head==null) {
            head = last = newNode;
        } else {
            last.next = newNode;
            newNode.prev = last;
            last = newNode;
        }
    }
    @Override
    public void addIndex(int index, int data) {
        if(index<0||index>size()) {
            System.out.println("index  违法");
            return;
        }
        if(index==0) {
            addFirst(data);
            return;
        }
        if(index==size()) {
            addLast(data);
            return;
        }
        int count = 0;
        ListNode curNode = head;
        ListNode node = new ListNode(data);
        while(count!=index) {
            curNode = curNode.next;
            count++;
        }
        node.prev = curNode.prev;
        node.next = curNode;
        curNode.prev.next = node;
        node.next.prev = node;

    }
//是否包含某个值
    @Override
    public boolean contains(int key) {
        ListNode curNode = head;
        while(curNode!=null) {
            if(curNode.val==key) {
                return true;
            }
            curNode = curNode.next;
        }
        return false;
    }
//删除某值
    @Override
    public void remove(int key) {
        if(head.val==key) {
            head.next.prev = null;
            head = head.next;
            return;
        }
        ListNode curNode = head;
        while (curNode!=null) {
            if(curNode.val==key) {
                break;
            }
            curNode = curNode.next;
        }
        if(curNode==null) {
            System.out.println("没有该值,无法删除");
            return;
        }
        curNode.prev.next = curNode.next;
        if(curNode!=last) {
            curNode.prev = curNode.prev;
        } else {
            last = last.prev;
        }
    }
//删除所有该值
    @Override
    public void removeAllKey(int key) {
        if(head==null) {
            return;
        }
        //移除链表头节点连续出现移除的数值
        while(head!=null&&head.val==key) {
            head = head.next;
        }
        if(head==null) {
            last = null;
            return;
        } else {
            head.prev = null;
        }
        ListNode cur = head;
        //处理中间和末尾出现移除节点的情况
        while (cur!=null) {
            if(cur.val == key) {
                cur.prev.next = cur.next;
                if(cur!=last) {
                    cur.next.prev = cur.prev;
                } else {
                    last = last.prev;
                }

            }
            cur = cur.next;
        }
    }
//得到链表长度
    @Override
    public int size() {
        int count = 0;
        ListNode curNode = head;
        while(curNode!=null) {
            count++;
            curNode = curNode.next;
        }
        return count;
    }

    @Override
    public void clear() {
        ListNode cur = head;
        while (cur!=null) {
            ListNode tmp = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = tmp;
        }
        head = null;
        last = null;
    }
//打印链表
    @Override
    public void display() {
        ListNode curNode = head;
        while(curNode!=null) {
            System.out.print(curNode.val+" ");
            curNode = curNode.next;
        }
        System.out.println();
    }
}


  • 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
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172

LinkedList

LinkedList引入

LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续空间中,元素存储在单独的节点中,然后通过引用将节点连接起来,因此在任意位置或者删除元素时,不需要移动元素,效率比较高

说明

  1. LinkedList实现了List接口
  2. LinkedList的底层使用双向链表
  3. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)
  4. LinkedList比较适合任意插入的场景

LinkedList的使用

LinkedList的构造

方法 解释
LinkedList() 无参构造
public LinkedList(Collection<? extends E> c) 使用其他集合容器中元素构造List

    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();

        List<Double> list1 = new LinkedList<>();
        list1.add(1.1);
        list1.add(2.1);

        List<Number> list2 = new LinkedList<>(list1);
        list2.add(3);
        list2.add(4);
        System.out.println(list2);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

在这里插入图片描述

LinkedList的常用方法介绍

方法 解释
boolean add(E e) 尾插 e
void add(int index, E element) 将 e 插入到 index 位置

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(0,6);
        
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述

boolean addAll(Collection<? extends E> c) 尾插 c 中的元素

        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(0,6);

        LinkedList<Number> list1 = new LinkedList<>();
        list1.add(2.3);
        list1.add(2);
        list1.addAll(list);

        for (int i = 0; i < list1.size(); i++) {
            System.out.print(list1.get(i)+" ");
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

在这里插入图片描述
E remove(int index) 删除 index 位置元素
boolean remove(Object o) 删除遇到的第一个 o
E get(int index) 获取下标 index 位置元素
E set(int index, E element) 将下标 index 位置元素设置为 element
void clear() 清空
boolean contains(Object o) 判断 o 是否在线性表中
int indexOf(Object o) 返回第一个 o 所在下标
int lastIndexOf(Object o) 返回最后一个 o 的下标
List subList(int fromIndex, int toIndex) 截取部分 list

LinkedList的遍历

LinkedList<Character> list = new LinkedList();
        list.add('a');
        list.add('b');
        list.add('c');
        list.add('d');
        //直接打印
        System.out.println(list);
        //foreach遍历
        for (Character c: list) {
            System.out.print(c+" ");
        }
        System.out.println();
        //for循环遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        //迭代器遍历
        ListIterator<Character> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

在这里插入图片描述

LinkedList<Character> list = new LinkedList();
        list.add('a');
        list.add('b');
        list.add('c');
        list.add('d');
        //直接打印
        System.out.println(list);
        //foreach遍历
        for (Character c: list) {
            System.out.print(c+" ");
        }
        System.out.println();
        //for循环遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        //迭代器正向遍历
        ListIterator<Character> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();
        //迭代器反向遍历
        while (it.hasPrevious()) {
            System.out.print(it.previous()+" ");
        }

  • 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

在这里插入图片描述

ArrayList和LinkedList的区别

不同点 ArrayList LinkedList
存储空间 物理上一定连续 逻辑上连续,物理上不一定连续
随机访问 O(1) O(N)
头插 需要移动元素,效率低O(N) 只需要改变引用的指向,O(1)
插入 空间不够需要扩容 没有扩容的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁

栈

概念

一种特殊的线性表,其只允许在固定的一段进行插入和删除元素操作.进行数据插入和删除操作的一段称为栈顶,另一端称为栈底,栈中的数据元素遵守后进先出的原则
压栈: 栈的插入操作叫作进栈/压栈/入栈,入数据在栈顶
出栈: 栈的删除操作叫作出栈.出数据在栈顶

栈的使用

方法 功能
Stack() 构造一个空的栈
E push(E e) 将e入栈，并返回e
E pop() 将栈顶元素出栈并返回
E peek() 获取栈顶元素
int size() 获取栈中有效元素个数
boolean empty() 检测栈是否为空

        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.size());
        int len = stack.size();
        for (int i = 0; i < len; i++) {
            System.out.print(stack.pop()+" ");
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

栈的模拟实现

栈接口


public interface IStack {
    void push(int val);
    int pop();
    int peek();
    int size();
    boolean empty();
    boolean full();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

栈实现
栈空的自定义异常

public class EmptyException extends RuntimeException{
    EmptyException(String s) {
        super(s);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5

public class MyStack implements IStack{
    private int[] arr;
    private int usedSize;
    public static final int DEFAULT_CAPACITY = 10;

    MyStack() {
        arr = new int[DEFAULT_CAPACITY];
    }
    @Override
    public void push(int val) {
        if(full()) {
            arr = Arrays.copyOf(arr,arr.length*2);
        }
        arr[usedSize++] = val;
    }

    @Override
    public int pop() {
        if(empty()) {
            throw new EmptyException("栈空,无法出栈");
        }
        usedSize--;
        return arr[usedSize];
    }

    @Override
    public int peek() {
        if(empty()) {
            throw new EmptyException("栈空,无法出栈");
        }
        return arr[usedSize-1];
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean full() {
        if(usedSize==arr.length) {
            return true;
        }
        return false;
    }

    @Override
    public boolean empty() {
        return 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

概念区分

栈:数据结构的一种
虚拟机栈:JVM划分的一块内存而已
栈帧:调用方法的时候,会在虚拟机中给这个方法开辟一块内存

队列

概念

队列: 只允许在一段进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特点.入队列: 进行插入操作的一端叫队尾, 出队列: 进行删除操作的一端称为队头

队列使用

方法 功能
boolean offer(E e) 入队列
E poll() 出队列
peek() 获取队头元素
int size() 获取队列中有效元素个数
boolean isEmpty() 检测队列是否为空

注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);

        System.out.println(queue.peek());
        System.out.println(queue.poll());
        System.out.println(queue.poll());

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述

队列模拟实现

public class MyLinkQueue {
        static class ListNode {
            public int val;
            public ListNode prev;
            public ListNode next;

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

        public ListNode head;//队头
        public ListNode tail;//队尾
        public int usedSize;
//入队列,在头节点处进行头插
        public boolean offer(int val) {
            ListNode node = new ListNode(val);
            if(head==null) {
                head = tail = node;
            } else {
                tail.next = node;
                node.prev = tail;
                tail = tail.next;
            }
            usedSize++;
            return true;
        }
//出队列--删除双向链表第一个节点
        public int poll() {
        //1.链表为空,返回自定义异常
        //2.队列中只有一个元素--链表中只有一个节点--直接删除
        //3.多个节点,删除第一个节点
            if(head==null) {
                throw new QueueNullException("队列为空");
            }
            int val = head.val;
            if(head.next==null) {
                head = null;
                tail = null;
                return val;
            }
            head = head.next;
            head.prev = null;
            usedSize--;
            return val;
        }
        //获取队头元素,获取链表中第一个节点的值
        public int peek() {
            if(head==null) {
                throw new QueueNullException("队列为空");
            }
            return head.val;
        }
        public boolean empty() {
            return head==null;
        }
        public int size() {
            return usedSize;
        }
}


  • 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

循环队列

在这里插入图片描述

如何区分空与满:

  1. 通过添加size属性记录
  2. 保留一个位置
  3. 使用标记

public class MyCircularQueue {
    private int[] elements;
    public int front;
    public int rear;

    private boolean flg;

    private int usedSize;

    public MyCircularQueue(int k) {
        elements = new int[k];
    }

    //入队
    public boolean enQueue(int value) {
        if(isFull()) {
           return false;
        }
        elements[rear] = value;
        rear = (rear+1)%elements.length;
        usedSize++;
//        flg = true;
        return true;
    }

    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        front = (front+1)%elements.length;
        usedSize--;
/*        if(front==rear) {
            flg = false;
        }*/
        return true;
    }

    public int Front() {
        if(isEmpty()) {
           return -1;
        }
        return elements[front];
    }

    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = (rear==0)?(elements.length-1):(rear-1);
        return elements[index];
/*        if(rear==0) {
            return elements[elements.length-1];
        } else {
            return elements[rear-1];
        }*/
    }

    public boolean isEmpty() {
        return front==rear&&usedSize==0;
//        return front==rear&&flg==false;
    }

    public boolean isFull() {
        return front==rear&&usedSize==elements.length-1;
//        return (rear+1)%elements.length==front;
    }
}


  • 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

双端队列

双端队列指的是在队列两边都可以进行入队和出队的操作
deque是"double ended queue"的简称
元素可以从队头出队或入队,也可以在队尾出队和入队
Deque是一个接口,使用时必须创建LinkedList对象

		Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
        Deque<Integer> queue  = new LinkedList<>();//双端队列的链式实现

  • 1
  • 2

用队列实现栈

队列是先进先出
栈是先进后出
用队列实现栈(leetcode原题)

使用两个队列实现
哪个栈不为空放在哪个栈,两个都为空,直到其中一个放进去
出栈的时候哪个不为空出哪个,直到size-1
当两个队列为空时,模拟的栈为空

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        Queue existQueue;
        Queue emptyQueue;
        if (queue2.isEmpty()) {
            existQueue = queue1;
            emptyQueue = queue2;
            existQueue.offer(x);
        } else {
            existQueue = queue2;
            emptyQueue = queue1;
            existQueue.offer(x);
        }
    }

    public int pop() {
        Queue existQueue;
        Queue emptyQueue;
        if (queue2.isEmpty()) {
            existQueue = queue1;
            emptyQueue = queue2;
        } else {
            existQueue = queue2;
            emptyQueue = queue1;
        }

        if (existQueue.size() == 0) {
            return -1;
        }
        if (existQueue.size() == 1) {
            int ret = (int) existQueue.peek();
            existQueue.poll();
            return ret;
        }
        int size = existQueue.size();
        while (size > 1) {
            emptyQueue.offer(existQueue.peek());
            existQueue.poll();
            size--;
        }
        int ret = (int) existQueue.peek();
        existQueue.poll();
        return ret;
    }

    public int top() {
        Queue existQueue;
        Queue emptyQueue;
        if (queue2.isEmpty()) {
            existQueue = queue1;
            emptyQueue = queue2;
        } else {
            existQueue = queue2;
            emptyQueue = queue1;
        }

        if (existQueue.size() == 0) {
            return -1;
        }
        if (existQueue.size() == 1) {
            int ret = (int) existQueue.peek();
            return ret;
        }
        int size = existQueue.size();
        while (size > 1) {
            emptyQueue.offer(existQueue.peek());
            existQueue.poll();
            size--;
        }
        int ret = (int) existQueue.poll();
        emptyQueue.offer(ret);
        return ret;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.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
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86

用栈实现队列

入队放到第一个栈里
出队都出第二个栈当中的元素,第二个栈没有元素,把第一个栈的元素倒进来
用栈实现队列题目

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    public MyQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if(!stack2.isEmpty()) {
            return stack2.pop();
        } else if(stack2.isEmpty()&&!stack1.isEmpty()) {
            int ret = -1;
            int size = stack1.size();
            for (int i = 0; i < size; i++) {
                ret = stack1.pop();
                stack2.push(ret);
            }
            return stack2.pop();
        } else {
            return -1;
        }
        
    }

    public int peek() {
        if(!stack2.isEmpty()) {
            return stack2.peek();
        } else if(stack2.isEmpty()&&!stack1.isEmpty()) {
            int ret = -1;
            int size = stack1.size();
            for (int i = 0; i < size; i++) {
                ret = stack1.pop();
                stack2.push(ret);
            }
            return ret;
        } else {
            return -1;
        }
    }

    public boolean empty() {
        return stack1.isEmpty()&&stack2.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
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号