顺序表(Arraylist)和链表(Linkedlist)

List

List是一个接口，继承自Collection。

从数据结构角度来说，List就是一个线性表，即用n个相同类型的有限序列，可以在此序列中可以进行增删改查操作。

List是接口不能直接实例化，Linkedlist和Arraylist都实现了List。

Arraylist

顺序表(Arraylist)是用一段物理地址连续的存储单元进行存储元素的线性结构，一般用数组进行实现，在数组上进行增删改查。

Arraylist使用

public static void main(String[] args) {
// ArrayList创建，推荐写法
// 构造⼀个空的列表
List<Integer> list1 = new ArrayList<>();// 构造⼀个具有10个容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整
形元素
// list3构造好之后，与list中的元素⼀致
ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略类型，否则：任意类型的元素都可以存放
List list4 = new ArrayList();
list4.add("111");
list4.add(100);
}

Arraylist常见操作

public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
list.add("JVM");
list.add("测试课程");
System.out.println(list);// 获取list中有效元素个数
System.out.println(list.size());// 获取和设置index位置上的元素，注意index必须介于[0, size)间
System.out.println(list.get(1));
list.set(1, "JavaWEB");
System.out.println(list.get(1));// 在list的index位置插⼊指定元素，index及后续的元素统⼀往后搬移⼀个位置
list.add(1, "Java数据结构");
System.out.println(list);// 删除指定元素，找到了就删除，该元素之后的元素统⼀往前搬移⼀个位置
list.remove("JVM");
System.out.println(list);// 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标
越界异常
list.remove(list.size()-1);
System.out.println(list);// 检测list中是否包含指定元素，包含返回true，否则返回false
if(list.contains("测试课程")){
list.add("测试课程");
}// 查找指定元素第⼀次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
list.add("JavaSE");
System.out.println(list.indexOf("JavaSE"));
System.out.println(list.lastIndexOf("JavaSE"));// 使⽤list中[0, 4)之间的元素构成⼀个新的SubList返回,但是和ArrayList共⽤⼀个
elementData数组
List<String> ret = list.subList(0, 4);
System.out.println(ret);
list.clear();
System.out.println(list.size());
}

ArrayList遍历

public static void main(String[] args) {Arraylistoj i = new Arraylistoj();i.generate(10);List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);for (int j = 0;j< list.size();j++){System.out.println(list.get(j));}for (int value:list) {System.out.println(value);}Iterator<Integer> lo = list.iterator();while(lo.hasNext()){System.out.println(lo.next());}}

模拟实现Arraylist

public class myArraylist {public int [] arr = new int[10];public int size;public myArraylist(int j){if(j>=10){this.arr = new int[j];}}public void add(int value) {if (size >= arr.length) {resize();}arr[size] = value;size++;}public void resize(){int[] newarr = new int[arr.length*2];for (int i = 0; i < size; i++) {newarr[i] = arr[i];}arr = newarr;}public void add(int index,int value){if(index<0||index>size){return;}if(size >= arr.length){resize();}for (int i = size-1; i >= index ; i--) {arr[i+1] = arr[i];}arr[index] = value;size++;}public void remove(int index){if(index<0||index>=size){throw new RuntimeException();}for (int i = index; i < size-1; i++) {arr[i] = arr[i+1];}size--;}public Boolean remove1(int value){int i = 0;for ( ;i < size; i++) {if(arr[i] == value){break;}}if(arr[i] == value){for (int j = i; j < size-1; j++) {arr[j] = arr[j+1];}}else{return false;}size--;return true;}public int get(int index){if(index<0||index>=size){throw new RuntimeException();}return arr[index];}public void set(int index,int values){if(index<0||index>=size){throw new RuntimeException();}arr[index] = values;}public void clean(){size=0;}public Boolean contins(int value){for (int i = 0; i < size; i++) {if(arr[i]==value){return true;}}return false;}public List<Integer> sublist(int left, int right){if(left<0||right>size){throw new RuntimeException();}ArrayList<Integer> l = new ArrayList<>();for (int i = left; i < right; i++) {l.add(arr[i]);}return l;}@Overridepublic String toString() {StringBuilder i = new StringBuilder();i.append("[");for (int j = 0; j < size; j++) {i.append(arr[j]);if(j<size-1){i.append(",");}}i.append("]");return i.toString();}

Linkedlist

ArrayList的缺陷

ArrayList在进行任意位置删除和插入元素，就需要将元素整体向后或向前移动，时间复杂度为O(n)，因此Arraylist不适合进行插入或删除元素比较多的时候。

链表

为解决上述问题，引入Linkedlist，链表是物理存储结构非连续的存储结构，逻辑上链表是通过链表引用链接连接的。

链表在逻辑上看是连续的，但在物理结构上并非连续。

节点一般从堆上申请的，从堆上申请的节点是按一定策略，可能连续，可能不连续。

链表的结构有多种：双向和单向，带头和非带头，循环和非循环。

链表的模拟实现

class Node{public int val;public Node next = null;public Node(int val) {this.val = val;}
}public class myLinklist {public Node head = null;public int size;public void addfirst(int value){Node newnode = new Node(value);newnode.next = head;head = newnode;size++;}public void addlist(int value){if(head==null){addfirst(value);return;}Node node = new Node(value);Node cur = head;for (;cur!=null;cur = cur.next){if(cur.next == null){break;}}cur.next = node;node.next = null;size++;}public void add(int index,int value){if(index<0||index>size){return;}if(index==size){addlist(value);size++;return;}if(index==0){addfirst(value);size++;return;}Node node = head;Node newnode = new Node(value);for (int i = 0; i < index-1; i++) {node = node.next;}newnode.next = node.next;node.next = newnode;size++;}public Boolean contins(int valus){Node node = head;for (;node!=null;node = node.next){if(node.val==valus){return true;}}return false;}public void remove(int index,int value){if(index<0||index>=size){return;}if(index==0){head=head.next;size--;return;}Node cur = head;Node pre = null;for (int i = 0; i < index; i++) {pre = cur;cur = cur.next;}pre.next = cur.next;size--;}public void remove(int curnode){if(head==null){return;}if(head.val==curnode){head = head.next;size--;return;}Node cur = head;Node prv = null;for (;cur!=null;){if(cur.val==curnode){break;}prv = cur;cur = cur.next;}prv.next = cur.next;size--;}public int indexOf(int value){Node node = head;int k = 0;for (;node!=null;node = node.next){if(node.val==value){return k;}k++;}return -1;}public void clean(){head = null;}@Overridepublic String toString() {StringBuilder o = new StringBuilder();o.append("[");Node i = head;for (;i!=null;i = i.next) {o.append(i.val);o.append(" ");if(i.next != null){o.append(",");}}o.append("]");return o.toString();}

Linkedlist介绍

Linkedlist实现了List。

Linkedlist的底层是双向链表。

Linkedlist没实现RandomAccess接口，表明不支持随机访问。

Linkedlist在随机插入和删除时，时间复杂度为O(1)。