目录

1.顺序表和链表区别

2.线性结构与非线性结构区别

3.图片展示

 二，List(列表)

1.什么是List

2.ArrayList，LinkedList ，Vector区别

1.ArrayList的优缺点

2.LinkedList的优缺点

3.Vector的优缺点

4.总结

3.List/Arraylist/LinkedList常用方法

4.详解ArrayList

(1).什么是ArrayList

(2).ArrayList的构造

(3).MyArrayList的实现

(4).例题

5.详解LinkedList

(1).什么是LInkedList

(2).什么是节点（Node类）

(3).LinkedList的构造

(4).遍历LinkedList

(5).MyLinkedList的简单实现

 (6).例题

线性表：由n(n>0)个数据元素(数字，字符等)所构成的有限序列，逻辑连续（一条直线），物理上不一定连续，分为顺序表和链表

1.顺序表和链表区别

1.顺序表：1.能存储的数据有限（一次开辟，永久使用），但是易于操作、编写代码

                  2.空间利用率相对高

                  3.若查改元素，其时间复杂度低O(1)，可根据数组下标直接访问；

                     若增删移其时间复杂度高，至少 O(n)，会牵涉到大量元素的整体移动

2.链表：    1.能存储的数据取决于堆的内存大小（存一个开辟一个空间）

                  2.空间利用率相对低，有空间碎片产生

                  3.若查改元素，其时间复杂度高，至少 O(n)，需要指针遍历找到指定节点；

                     若增删移其时间复杂度低O(1)，在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可

2.线性结构与非线性结构区别

  1.线性：数据元素存在一对一的对应关系，有两种不同的存储结构，顺序存储结构（数组，顺序表）和链式存储结构（链表），常见的有数组，队列，链表和栈

  2.非线性： 数据元素不再保存在一个线性序列中，可一对零/多，常见的有二维数组，多维数组，广义表，树(二叉树等)

3.图片展示

 图1来自 UniqueUnit 

 图2来自Fei@ 

 二，List(列表)

1.什么是List

（1）List 是接口，继承至Collection接口，使用时必须去实例化List的实现类ArrayList,LinkedList

（2）List包含，ArrayList,  LinkedList ,  Vector

2.ArrayList，LinkedList ，Vector区别

1.ArrayList的优缺点

ArrayList是基于动态的数组的数据结构

优点：底层数据结构是数组，查询快，增删慢。

缺点： 线程不安全，效率高

2.LinkedList的优缺点

LinkedList是基于链表的数据结构

优点：底层数据结构是链表，查询慢，增删快。

缺点： 线程不安全，效率高

3.Vector的优缺点

在ArrayList中每个方法中添加了synchronized关键字来保证同步

优点：底层数据结构是数组，查询快，增删慢。

缺点：线程安全，效率低

4.总结

查询次数多：ArrayList

修改次数多：LinkedList

安全性高：Vector

3.List/Arraylist/LinkedList常用方法

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

4.详解ArrayList

(1).什么是ArrayList

在集合框架中，ArrayList是一个普通的类，是List接口的大小可变数组的实现（结构体+数组）

特点：1.支持随机访问
           2.可以clone
           3. 支持序列化
           4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
           5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表                         6.自动扩容(Arrays.copyOf(elem,2*elem.length))

(2).ArrayList的构造

空列表：                    List   list1 =    new     ArrayList<>(); 

具有10个容量：         List   list2  = new ArrayList<>(10);

与list2中的元素一致：ArrayList  list3  = new ArrayList<>(list2);

注意：一定不能省略类型，若任何类型的元素都可以存放，将会发生混乱

(3).MyArrayList的实现

import java.util.Arrays;
public class MyArraylist {

    public int[] elem;
    public int usedSize;//默认容量
    private static final int DEFAULT_SIZE = 10;

    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
        this.usedSize=0;
    }

   //打印顺序表
    public void display() {
        for (int i = 0; i this.usedSize){
            System.out.println("pos位置不合法");
            return false;
        }
        return true;//合法
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if(isFull()){
            //数组满了，就扩容
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        for(int i=this.usedSize-1;i>=pos;i--){
            this.elem[i+1]=elem[i];
        }
        this.elem[pos]=data;
        this.usedSize++;
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for(int i=0;i 
(4).例题 
力扣   杨辉三角
 
答案：
 
class Solution {   
public static List> generate(int num){

        List> list=new ArrayList<>();
        int[][]array=new int[num][num];

        for (int i = 0; i < num; i++) {

            List subList=new ArrayList<>();
            for(int j=0;j<=i;j++){
                if(j==0||j==i){
                    array[i][j]=1;
                }else{
                    array[i][j]=array[i-1][j-1]+array[i-1][j];
                }
                subList.add(array[i][j]);
            }

            list.add(subList);
        }
        return list;
    }
}
 
5.详解LinkedList 
(1).什么是LInkedList 
  链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用（指针）链接次序实现的,是List接口链表的实现（结构体+指针）
 
  简述：通过节点连接元素的序列
 
特点：
 
        1.逻辑连续，物理不一定连续
 
        2.现实中的结点一般都是从堆上申请出来的
 
        3.空间分配具有策略，两次申请的空间可能一样，也可能不一样
 
        4.底层使用了双向链表
 
        5.不支持随机访问
 
        6.插入和删除元素，时间复杂度为O(1)
 
分类：
 
        1.单向or双向
 
 
         2.带头or不带头
 
 
        3.循环or非循环
 
 
(2).什么是节点（Node类） 
  1.链表由一系列节点（链表中每一个元素称为结点）组成，节点可以在运行时动态生成。
 
  2.每个节点包括两个部分：存储数据元素的数据域，存储下一个节点地址的指针域。
 
     如图：
 
 
  3.代码实现
 
private static class Node {
    E val;//所存数据
    Node next;//指向下一个节点的引用（指针）
    Node prev;//指向上一个节点的引用（指针）

    Node(E val, Node next, Node prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}
 
(3).LinkedList的构造 
 
 
构造一个空的LinkedList： List list1 = new LinkedList<>();
 
 
 
 
使用ArrayList构造LinkedList：
 
 
List list2 = new java.util.ArrayList<>();
 
 
List list3 = new LinkedList<>(list2);
 
 
(4).遍历LinkedList 
1.foreach遍历
 
 
 
for (int e:list) {
     System.out.print(e + " ");
  }
 
 
2.迭代器遍历
 
 
 
 ListIterator it = list.listIterator();
   while(it.hasNext()){
     System.out.print(it.next()+ " ");
  }
 
 
3.反向迭代器遍历
 
 
 
 ListIterator rit = list.listIterator(list.size());
   while (rit.hasPrevious()){
     System.out.print(rit.previous() +" ");
  } 
 
 
(5).MyLinkedList的简单实现 
public class MySingleLinkedList >{
    protected Node head;//指向当前链表的第一个节点

    public Node getHead() {
        return head;
    }

    //自定义的节点类型
    class Node{
        protected T data;
        protected Node next;
        public Node(T data){
            this.data =data;
        }
    }

    //增加一个节点到链表中
    public void add(T data){
        Node newNode = new Node<>(data);
        if(head == null){
            //空的链表
            head = newNode;
        }else{
            //链表非空的情况，需要找到尾节点
            Node tmp = head;
            while(tmp.next != null){
                tmp = tmp.next;
            }
            //跳出while循环表示tmp指向的就是尾节点
            //将尾节点的next置为新节点
            tmp.next = newNode;
        }
    }
    //从链表中删除一个节点
    public boolean delete(T data){
        if(data == head.data){
            Node tmp = head;
            tmp = null; //方便垃圾回收
            head = head.next;
            return true;
        }
        //删除的一个普通节点
        //找到所要删除的节点，找到所要删除节点的前一个节点/后一个节点
        Node tmp = head;
        while(tmp.next != null){
            //找所要删除节点 即为tmp.next
            if(tmp.next.data == data){
                tmp.next = tmp.next.next;
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }

    public T findNode(int index){
        //下标合法性判断
        if(index < 0 ) return null;
        Node tmp = head;
        for(int i=0; i tmp = head;
        while(tmp != null){
            strs.append(tmp.data+" ");
            tmp = tmp.next;
        }
        return strs.toString();
    }
}
 
(6).例题