我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

Java_简单实现无头单向非循环链表_简单实现LinkedList_无头单向非循环链表 java实现

作者：我家小花儿 | 2024-05-29 12:50:19

踩

无头单向非循环链表 java实现

文章目录

一、ArrayList的优缺点
二、链表
三、实现无头单向非循环链表
四、练习
五、模拟实现LinkedList
六、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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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() {

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

3.成员

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

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

   static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val)
        {
            this.val = val;
        }
    }
1
2
3
4
5
6
7
8

2、头节点引用

 public ListNode head;
1

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");
    }
1
2
3
4
5
6
7
8
9
10

5.得到单链表的长度 size

    @Override
    public int size() {
        ListNode cur= head;
        int ret = 0;
        while(cur!=null)
        {
            ret++;
            cur = cur.next;
        }
        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

7.头插法 addFirst

    @Override
    public void addFirst(int data) {
        ListNode newhead = new ListNode(data);
        newhead.next = head;
        head = newhead;
    }
1
2
3
4
5
6

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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;

        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

    public void clear() {
        while(head!=null)
        {
            head.val = 0;//如果用泛型就是null
            head.next = null;
            head = head.next;
        }
    }
1
2
3
4
5
6
7
8

四、练习

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

五、模拟实现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(){}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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() {

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

3.成员

1、节点类

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

    class ListNode {
        public int val;
        public  ListNode prev;
        public ListNode next;
        public ListNode(int val)
        {
            this.val = val;
        }
    }
1
2
3
4
5
6
7
8
9

2、头引用和尾引用

    public ListNode head;
    public ListNode last;
1
2

4.打印链表 display

    public void display() {
        ListNode cur = head;
        while(cur!=null)
        {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7
8
9
10
11
12
13

6.头插法 addFirst

    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        node.prev = node;
        head = node;
    }
1
2
3
4
5
6

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

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

9.得到单链表的长度 size

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

        return count;
    }
1
2
3
4
5
6
7
8
9
10
11

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;


        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

六、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();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

在这里插入图片描述

2.ArrayList和LinkedList的区别？

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/642207

Java_简单实现无头单向非循环链表_简单实现LinkedList_无头单向非循环链表 java实现

文章目录

一、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的区别？

五、模拟实现LinkedList