---

一、ArrayList的优缺点

缺点：
1.插入数据必须移动其他数据，最坏情况下，就是插入到0位置。时间复杂度O(N)
2.删除数据也需要移动数据，最坏情况下，就是删除0位置。时间复杂度O(N)
3.扩容之后，有可能会浪费空间
优点：
1.在给定下标进行查找的时候，时间复杂度O(1)
总结：顺序表比较适合进行给定下标查找的场景

二、链表

1.链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。就像火车一样是一节一节的。

火车之间用挂钩相连，每个节点都存储下一个节点的物理地址。

2.链表的分类

1、单向或者双向

2、带头或者不带头

3、循环或者非循环

无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

三、实现无头单向非循环链表

1.定义接口

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

2.定义MySingleList

public class MySingleList implements IList{
    @Override
    public void addFirst(int data) {
        
    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

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

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }
}

3.成员

1、节点类（定义在MySingList类里）

节点类包含存储数据和下一个节点引用。

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

2、头节点引用

 public ListNode head;

4.打印链表实现dispaly(这是方便测试写的)

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

5.得到单链表的长度 size

    @Override
    public int size() {
        ListNode cur= head;
        int ret = 0;
        while(cur!=null)
        {
            ret++;
            cur = cur.next;
        }
        return ret;
    }

6.查找是否包含关键字key是否在单链表当中 contions

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

7.头插法 addFirst

    @Override
    public void addFirst(int data) {
        ListNode newhead = new ListNode(data);
        newhead.next = head;
        head = newhead;
    }

8.尾插法 addLast

    @Override
    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;
        }
    }

9、任意位置插入,第一个数据节点为0号下标 addIndex

    private  ListNode searchPrev(int index)
    {
        ListNode cur = head;
        int count = index-1;
        while(count--!=0)
        {
            cur = cur.next;
        }
        return cur;
    }
    @Override
    public void addIndex(int index, int data) {
        if(index<0||index>size())
        {
            return;
        }
        ListNode temp = new ListNode(data);
        if(index==0)
        {
            temp.next= head;
            head=temp;
        }
        else
        {
            ListNode cur= searchPrev(index);
            temp.next = cur.next;
            cur.next =temp;

        }

    }

10、删除第一次出现关键字为key的节点 remove

    public void remove(int key) {
        if(head==null)
        {
            return;
        }
        if(head.val==key)
        {
            head = head.next;
            return;
        }
        else
        {
            ListNode cur = head;
            while(cur.next!=null)
            {
                if(cur.next.val==key)
                {
                    cur.next = cur.next.next;
                    return;
                }
                cur= cur.next;
            }
        }
        return;
    }

11.删除所有值为key的节点 removeAllKey

   @Override
    public void removeAllKey(int key) {
        if(head==null)
        {
            return;
        }
        while(head.val==key)
        {
            head = head.next;
        }

        ListNode cur = head;
        while(cur.next!=null)
        {
            if(cur.next.val==key)
            {
                cur.next = cur.next.next;

            }
            else
            {
                cur=cur.next;
            }
        }

        return;
    }

12.删除所有值为key的节点 clear

    public void clear() {
        while(head!=null)
        {
            head.val = 0;//如果用泛型就是null
            head.next = null;
            head = head.next;
        }
    }

四、练习

1.移除链表元素

移除链表元素
我这里创了一个头节点headnode，这样后面包括head都可以用一样处理方式，最后返回头节点的下一个节点。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode headnode = new ListNode();
        headnode.next = head;
        ListNode cur = headnode;
        while(cur.next!=null)
        {
            if(cur.next.val==val)
            {
                cur.next = cur.next.next;
            }
            else 
            {
                cur= cur.next;
            }
        }

        return headnode.next;
    }
}

2.反转链表

反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null)
        {
            ListNode temp = cur.next;
            cur.next =pre;
            pre =cur;
            pre = cur;
            cur =temp;
        }
        return pre;
    }
}

3.链表的中间节点

快慢指针：快的一步跳俩节点，慢的跳一节点，当快的到尾，慢的就到了中间。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode low = head;

        while(fast!=null)
        {
            if(fast.next!=null)
            {
                fast = fast.next;
                low = low.next;
            }
            fast = fast.next;
        }
        return low;

    }
}

4.链表中倒数第k个节点

链表中倒数第k个节点

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode cur = head;
        int count = 0;
        while(cur!=null)
        {
            count++;
            cur= cur.next;
        }
        
        ListNode ret = head;
        count=count-k;
        if(count<0)
        {
            return null;
        }
        while(count--!=0)
        {
            ret = ret.next;
        }
        
        return ret;
    }
}

5.合并两个有序链表

合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode head = new ListNode();
        ListNode end = head;
        while(cur1!=null&&cur2!=null)
        {
            if(cur1.val>cur2.val)
            {
                end.next = cur2;
                cur2 = cur2.next;
            }
            else
            {
                end.next = cur1;
                cur1 =cur1.next;
            }
            end = end.next;        
        }
            if(cur1==null)
            {
                end.next = cur2;
            }
            else if(cur2==null)
            {
                end.next = cur1;
            }
        
        return head.next;
    }
}

6.链表分割

链表分割
注意要把大于k的节点最后一个的next置为null可能会出现环

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode smallHead = new ListNode(0);
        ListNode bigHead = new ListNode(0);
        ListNode smallCur = smallHead;
        ListNode bigCur = bigHead;
        ListNode cur = pHead;
        while(cur!=null)
        {
            if(cur.val<x)
            {
                smallCur.next = cur;
                smallCur =smallCur.next;
            }
            else
            {
                bigCur.next =cur;
                bigCur = bigCur.next;
            }
            cur = cur.next;
        }
        bigCur.next = null;
        smallCur.next = bigHead.next;
        return smallHead.next;
    }
}

7.链表回文结构

链表回文结构
1、用快慢指针找到中间节点
2、反转后面节点
3、从两边向中间验证是否是回文

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        ListNode fast = A;
        ListNode slow = A;
        while(fast!=null&&fast.next!=null)
        {
            fast= fast.next.next;
            slow =slow.next;
        }
        ListNode pre = slow;
        slow = slow.next;
        while(slow!=null)
        {
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        slow =A;
        while(slow!=pre)
        {
            if(slow.val!=pre.val)
            {
                return false;
            }
            if(slow.next==pre)
            {
                break;
            }
            slow = slow.next;
            pre = pre.next;
            
        }
        return true;

    }
}

8.相交链表

相交链表
1、先测出两链表的长度
2、遍历俩链表，让较长的先走相差长度的步数
3、比较节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int countA=0,countB=0;
        while(curA!=null)
        {
            countA++;
            curA =curA.next;
        }
        while(curB!=null)
        {
            countB++;
            curB =curB.next;
        }
        curA = headA;
        curB = headB;
        if(countA>countB)
        {
            int differ = countA-countB;
            while(differ--!=0)
            {
                curA = curA.next;
            }
        }
        else
        {
            int differ = countB-countA;
            while(differ--!=0)
            {
                curB = curB.next;
            }
        }

        while(curA!=null)
        {
            if(curA==curB)
            {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

9.环形链表

环形链表
快慢指针，相遇即为环形

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null)
        {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null)
        {
            fast = fast.next.next;
            slow =slow.next;
            if(fast==slow)
            {
                return true;
            }
        }
        return false;
    }
}

10.环形链表2

环形链表2
在快慢相遇时，在开头在创建指针，和相遇慢指针一起走，再次相遇即为环形节点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow =head;
        while(fast!=null&&fast.next!=null)
        {
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow)
            {
                break;
            }
        }
        if(fast==null||fast.next==null)
        {
            return null;
        }
        ListNode cur = head;
        while(cur!=slow)
        {
            cur = cur.next;
            slow = slow.next;
        }
        return cur;
    }
}

五、 模拟实现LinkedList

LinkedList是无头双向链表

1.定义接口

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

2.定义MyLinkedList

public class MyLinkedList implements IList{

    @Override
    public void addFirst(int data) {

    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

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

    @Override
    public void display() {

    }

    @Override
    public void clear() {

    }
}

3.成员

1、节点类

存储数据，指向前一个节点的引用，指向后一个节点的引用。

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

2、头引用和尾引用

    public ListNode head;
    public ListNode last;

4.打印链表 display

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

5.查找是否包含关键字key是否在单链表当中 contions

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

6.头插法 addFirst

    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        node.prev = node;
        head = node;
    }

7.尾插法 addLast

    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head==null)
        {
            head =node;
            last = node;
        }
        else
        {
            last.next = node;
            node.prev = last;
            last = node;
        }

    }

8.任意位置插入,第一个数据节点为0号下标 addIndex

    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 = index-1;
        ListNode cur = head;
        while(count--!=0)
        {
            cur = cur.next;
        }
        ListNode node =new ListNode(data);
        node.prev = cur;
        node.next = cur.next;
        cur.next.prev =  node;
        cur.next = node;
    }

9.得到单链表的长度 size

   public int size() {
        ListNode cur =head;
        int count =0;
        while(cur!=null)
        {
            count++;
            cur =cur.next;
        }

        return count;
    }

10.删除第一次出现关键字为key的节点 remove

注意以下特殊情况：
1、删除头一个情况
2、删除头一个情况且只有一个节点
3、删除最后一个

   public void remove(int key) {
        ListNode cur  = head;
        while(cur!=null)
        {
            if(cur.val==key)
            {
                if(cur==head){
                    head = head.next;
                    if(head==null)
                    {
                        last = null;
                    }
                    else {
                        head.prev =null;
                    }
                }
                else
                {
                    cur.prev.next = cur.next;
                    if(cur.next==null)
                    {
                        last = last.prev;
                    }
                    else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }
            cur =cur.next;


        }

    }

11.删除所有值为key的节点 removeAllKey

同上但删除不return

    public void removeAllKey(int key) {
        ListNode cur  = head;
        while(cur!=null)
        {
            if(cur.val==key)
            {
                if(cur==head){
                    head = head.next;
                    if(head==null)
                    {
                        last = null;
                    }
                    else {
                        head.prev =null;
                    }
                }
                else
                {
                    cur.prev.next = cur.next;
                    if(cur.next==null)
                    {
                        last = last.prev;
                    }
                    else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur =cur.next;
        }
    }

12.清空 clear

    public void clear() {
        ListNode cur = head;
        while(cur!=null)
        {
            cur.prev = null;
            cur.val =-1;//如果是引用要置空null
            ListNode temp = cur.next;
            cur.next = null;
            cur = temp;
        }
        head =null;
        last =null;
    }

六、LinkedList

1.遍历

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

        System.out.println("========");
        ListIterator<Integer> it = list.listIterator();
        while(it.hasNext())
        {
            System.out.print(it.next()+" ");
        }
        System.out.println();

        ListIterator<Integer> it2 = list.listIterator(list.size());
        while(it2.hasPrevious())
        {
            System.out.print(it2.previous()+" ");
        }
        System.out.println();
    }

2.ArrayList和LinkedList的区别？