【数据结构】顺序表和链表重点知识汇总（附有代码）-易微帮

思维导图：

1.List的介绍和使用：

List是一个接口不能直接实例化，List继承于Collection。
List是一个线性表，是有相同类型元素的有限序列。

ArrayList和LinkedList都实现了List接口。

//只能访问 List 当中的方法
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new LinkedList<>();
List<Integer> list3 = new Stack<>();

//可以访问接口中的方法，也可以访问自己类中的方法
ArrayList<Integer> list4 = new ArrayList<>();
LinkedList<Integer> list5 = new LinkedList<>();
Stack<Integer> list6 = new Stack<>();

2.线性表：

线性表是有多个相同特性元素的有限序列，在数据结构中广泛使用。常见的线性表有数组、顺序表、链表、栈和队列等。
线性表的结构特点。从逻辑结构和物理结构上来说，在逻辑上是线性结构，类似于一条直线。而在物理上也可以称为内存上，确是不一定连续的，比如连续的有顺序表，链式结构的有链表。
线性表的存储方式有顺序存储和链式存储。

3.ArrayList：

ArrayList是一个类，实现了List接口。
ArrayList是一个动态类型的顺序表，体现在增加元素时会自动发生扩容。
ArrayList底层是一块连续的内存空间，就是采用数组的存储形式，其背后就是一个数组。
如果创建了一个ArrayList但是没有指定容量的话，这个顺序表默认的大小为0，当add ();元素时ArraysList就会扩容到10，以后每次按照1.5倍扩容。例如：原来大小是10，扩容后变成15。
检测到要扩容时会调用grow方法，源码中是调用copyOf进行扩容。

ArrayList有3种创建方法

3种创建方法	说明
List<Integer> list1 = new ArrayList<>()；	推荐写法
List<Integer> list2 = new ArrayList<>(66)；	可以指定顺序表的容量
List<Integer> list3 = new ArrayList<>(list2)；	List3中的元素和list2一样

ArrayList的模拟实现

public class MyArrayList {

    public int[] elem;
    public int usedSize;//当前顺序表中元素的个数
    private static final int DEFAULT_CAPACITY = 10;//给定一个默认的容量

    public MyArrayList(){
        elem = new int[DEFAULT_CAPACITY];
    }

    //打印顺序表
    public void diaplay(){
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }
    //判断顺序表有没有满
    private boolean isFull(){
        return usedSize == elem.length;
    }

    //增加元素时检查下标是否合法
    private void checkPos1(int pos) {
        if(pos < 0 || pos > usedSize){
            return;
        }
    }

    //修改查找元素时检查下标是否合法
    private void checkPos2(int pos){
        if(pos<0 || pos >= usedSize){
            return;
        }
    }
    //增加元素（尾插）
    public void add(int data){
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = data;
        usedSize++;
    }

    //在pos位置上增加元素
    public void add(int pos,int data){
        checkPos1(pos);
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        //注意是 i>=pos
        for (int i = usedSize-1; i >= pos; i--) {
            elem[i+1] = elem[i];
        }
        elem[pos] = data;
        usedSize++;
    }

    //判断是否包含某个元素
    public boolean contains(int data){
        //i最多会走到usedSize的前一个元素，所以usedSize不用-1
        for (int i = 0; i < usedSize; i++) {
            if(data == elem[i]){
                return true;
            }
        }
        return false;
    }

    //找到某个元素的下标
    public int indexOf(int data){
        for (int i = 0; i < usedSize; i++) {
            if(data == elem[i]){
                return i;
            }
        }
        return -1;
    }

    //获取pos下标的元素
    public int get(int pos){
        checkPos2(pos);
        return elem[pos];
    }

    //将pos位置的值改成value
    public void set(int pos,int value){
        checkPos2(pos);
        elem[pos] = value;
    }

    //删除第一次出现的关键字key
    public void remove(int key){
        int index = indexOf(key);
        if(index == -1){
            System.out.println("找不到这个数字");
        }
        checkPos2(index);
        //这里注意一下：一定要-1
        for (int i = index; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

    //获取顺序表的长度
    public int size(){
        /*int count = 0;
        for (int i = 0; i < usedSize; i++) {
            count++;
        }
        return count;*/
        return usedSize;
    }

    //清空顺序表
    public void clear(){
        /*for (int i = 0; i < usedSize; i++) {
            elem[i]=null;
        }*/
        usedSize = 0;
    }

}

4.ArrayList的常见操作：

增加元素

增加元素	说明
add（x）；	尾插元素x
add（index，x）；	将元素x插入到下标为index的位置
addAll（c）；	将c中的元素插入到顺序表的末尾

删除元素

删除元素	说明
remove（index）；	删除index处的下标
remove（x）;	删除第一个元素为x
clear（）；	清空顺序表

查找元素

查找元素	说明
get（index）；	获取下标为index的元素
contains（x）;	判断元素x是否在顺序表中
indexOf（x）;	返回第一个元素为x的下标
lastIndexOf（x）;	返回最后一个元素为x的下标

修改元素

修改元素	说明
set（index，x）；	将下标为index的元素改为x
subList（first，last）；	截取下标从first到last的部分顺序表

对subList（）；截取的部分的值修改，也会影响到原顺序表的值。因为subList（）；截取后返回的是该起始点的地址。

5.ArrayList的遍历：

有4种遍历方法

//直接打印
System.out.println(list);

//for循环+下标
for( int i = 0; i<list.size() ; i++ ) {
    System.out,println( list.get(i) );
}

//foreach实现
for( Integer integer : list ) {
    System.out, println(integer + " ");
}

//使用迭代器1
Iterator<Integer> it = list.listIterator();
while (it.hasNext()) {
    System.out.println(it.next() + " ");
}

//使用迭代器2
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

只要实现了Iterable接口的，就可以使用迭代器来打印。

6.顺序表的缺陷：

增删查改，使用顺序表进行数据的插入、查找和删除其时间复杂度都是O(n)，效率太低！例如：插入和删除某个元素，需要移动其他元素。
顺序表的开辟需要一块连续的空间，空间利用率较低。
扩容问题，扩容一般是1.5倍增长，容易造成一定空间的浪费。例如：当前容量100，扩容到了150，但是我只存了9个元素，剩下的41个数据空间就浪费了......

(下面是链表部分)

7.链表的结构：

从物理结构上看（内存上），链表是非连续的结构；从逻辑结构上看链表又是连续的。
链表分为单向、双向、带头、不带头、循环和非循环。
组合起来一共就有8种链表结构。
最难掌握也是最重要的是单向不带头非循环链表。

8.单链表：

单链表的结构特点，单向链表存放当前元素值val和下一个元素的地址next，最后一个元素的next为null。

无头单向非循环链表的模拟实现

public class MySingleList {

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

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

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

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

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

    //从指定节点打印
    public void display(ListNode newHead){
        ListNode cur = newHead;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找元素key是否在单链表中
    public boolean contains(int key){
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

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

    //插入元素时检查下标合法性
    private void checkIndex(int index) {
        if(index < 0 || index > size()){
            return;
        }
    }

    //任意位置插入元素,首元素若为0下标
    public void addIndex(int index,int data){
        checkIndex(index);
        if(index == 0){
            addFirst(data);
            return;
        } else if (index == size()) {
            addLast(data);
            return;
        }else {
            ListNode node = new ListNode(data);
            ListNode cur = head;
            while (index - 1 != 0) {
                cur = cur.next;
                index--;
            }
            node.next = cur.next;
            cur.next = node;
        }

    }

    //删除第一次出现的元素key
    public void remove(int key){
        if(head.val == key){
            head = head.next;
            return;
        }
        ListNode cur = head;
        //循环中时cur.next，如果是cur的话会空指针异常
        while(cur.next != null){
            //这里处理不了头节点
            if(cur.next.val == key){
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }

    //删除所有值为key的元素。只遍历了一遍！！
    public void removeAll(int key){
        if(head == null){
            return;
        }
        ListNode cur = head;
        ListNode prev = head;

        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key){
            head = head.next;
        }
    }

    //清空链表
    public void clear(){
        ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }

}

9.LinkedList：

LinkedList底层是一个双向链表，可以当作栈和队列来使用。
LinkedList的特点，LinkedList没有实现RandomAccess接口因此不支持随机访问，而顺序表ArrayList实现了接口因此支持随机访问。

10.LinkedList常见的操作方法：

增加元素

增加元素	说明
add（x）；	尾插元素 x
add（index，x）；	将x插入到 index下标
addAll（c）；	将c中的元素全部尾插

删除元素

删除元素	说明
remove（index）；	删除index下标元素
remove（x）；	删除遇到的第一个x元素
clear（）；	清空链表

查找元素

查找元素	说明
get（index）；	获取index下标元素
contains（x）;	判断链表中是否包含x
indexOf（x）;	返回遇到的第一个x元素下标
lastIndexOf（x）；	返回最后一个值为x的元素的下标

修改元素

修改元素	说明
set（index，x）；	将index下标元素修改为x
subList（first，last）；	截取first下标到last下标之间的元素

11.LinkedList的遍历：

有4种打印方法

//直接打印
System.out.println(linkedlist);

//for循环+下标
for( int i = 0; i < linkedlist.size(); i++ ) {
    System.out,println( linkedlist.get(i) );
}

//foreach实现
for( Integer integer : linkedlist ) {
    System.out, println(integer + " ");
}

//使用迭代器
ListIterator<Integer> it = linkedlist.listIterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

12.ArrayList和LinkedList异同：

结构上，ArrayList在物理结构和逻辑结构上是连续的，而LinkedList在逻辑结构上连续，物理结构上不一定连续。
因为ArrayList实现了RandomAccess接口所以支持随机访问，而LinkedList不可以。知道元素下标时ArrayList可以更快访问，时间复杂度为O(1)；LinkedList查找访问元素时效率低，时间复杂度为O(n)。
修改、删除和插入元素时，ArrayList的效率很低，有一种“牵一发而动全身”的感觉，因此时间复杂度为O(n)。LinkedList在处理增删改的时候只需要改动部分的next即可，效率很高。
ArrayList还有一个特点，他是动态类型的顺序表，其容量和扩容都是固定的操作，很浪费空间，空间利用率也不高。而LinkedList没有扩容一说，如果需要增加元素只需要插入并且修改next的地址即可，空间利用率很高。
如果需要频繁的查找访问元素，可以使用ArrayList来完成。如果需要大量的插入删除元素，那么使用LinkedList会更好。

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

本文含有隐藏内容，请开通VIP 后查看

【数据结构】顺序表和链表重点知识汇总（附有代码）

思维导图：

目录

1.List的介绍和使用：

2.线性表：

3.ArrayList：

4.ArrayList的常见操作：

5.ArrayList的遍历：

6.顺序表的缺陷：

7.链表的结构：

8.单链表：

9.LinkedList：

10.LinkedList常见的操作方法：

11.LinkedList的遍历：

12.ArrayList和LinkedList异同：

网站公告

今日签到

热门文章

最新发布