文章目录
- 一、ArrayList的优缺点
- 二、链表
- 1.链表的概念及结构
- 2.链表的分类
- 1、单向或者双向
- 2、带头或者不带头
- 3、循环或者非循环
- 三、实现无头单向非循环链表
- 1.定义接口
- 2.定义MySingleList
- 3.成员
- 1、节点类（定义在MySingList类里）
- 2、头节点引用
- 4.打印链表实现dispaly(这是方便测试写的)
- 5.得到单链表的长度 size
- 6.查找是否包含关键字key是否在单链表当中 contions
- 7.头插法 addFirst
- 8.尾插法 addLast
- 9、任意位置插入,第一个数据节点为0号下标 addIndex
- 10、删除第一次出现关键字为key的节点 remove
- 11.删除所有值为key的节点 removeAllKey
- 12.删除所有值为key的节点 clear
- 四、练习
- 1.移除链表元素
- 2.反转链表
- 3.链表的中间节点
- 4.链表中倒数第k个节点
- 5.合并两个有序链表
- 6.链表分割
- 7.链表回文结构
- 8.相交链表
- 9.环形链表
- 10.环形链表2
- 五、 模拟实现LinkedList
- 1.定义接口
- 2.定义MyLinkedList
- 3.成员
- 1、节点类
- 2、头引用和尾引用
- 4.打印链表 display
- 5.查找是否包含关键字key是否在单链表当中 contions
- 6.头插法 addFirst
- 7.尾插法 addLast
- 8.任意位置插入,第一个数据节点为0号下标 addIndex
- 9.得到单链表的长度 size
- 10.删除第一次出现关键字为key的节点 remove
- 11.删除所有值为key的节点 removeAllKey
- 12.清空 clear
- 六、LinkedList
- 1.遍历
- 2.ArrayList和LinkedList的区别？
一、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的区别？
![[晓理紫]每日论文分享(有中文摘要，源码或项目地址)--强化学习、模仿学习](https://img-blog.csdnimg.cn/direct/da94ca7618744edb99fd7e58050a1339.jpeg#pic_center)
