devbox
小舞很执着
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java 单链表知识点总结及代码实现_java单链表

作者：小舞很执着 | 2024-07-01 18:45:00

赞

踩

java单链表

JAVA实现单链表

本文是通过JAVA实现单链表的基本功能

一、实现功能

单链表的：

  1. 头部增加、头部删除
  2. 尾部增加、尾部删除
  3. 改变节点数据
  4. 输出倒数第k个节点
  5. 链表逆置
  6. 判断是否有环，找到环的入口
  7. 找到两个单链表的第一个交点
  8. 合并有序单链表

循环单链表的：

  1. 头部增加、头部删除
  2. 尾部增加、尾部删除
  3. 删除指定值节点

二、代码部分

单链表

1.链表节点类
public class Entry<T extends Comparable<T>> {
        private T value;
        private Entry<T> next;
        public Entry(T value) {
            this.value = value;
        }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public Entry<T> getNext() {
        return next;
    }

    public void setNext(Entry<T> next) {
        this.next = next;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
2.单链表类
public class Link<E extends Comparable<E>>{
    public Entry<E> headEntry;//头节点
    private int length = 0;
    public Link(){
        headEntry = new Entry<>(null);
    }
    //头部增加
    public void headAdd(E value){
        Entry<E> entry = new Entry<E>(value);
        if(length == 0){
            headEntry=entry;
        }else{
            entry.setNext(headEntry);
            headEntry=entry;
        }
        length++;
    }
    //头部删除
    public void headDelete(){
        if(length != 0){
            headEntry.setValue(null);//内存泄漏
            headEntry = headEntry.getNext();
            length--;
        }
    }
    //尾部添加
    public void endAdd(E value){
        Entry<E> entry = new Entry<E>(value);
        Entry<E> p;
        for(p = headEntry;p.getNext() != null;p=p.getNext()){ }
        p.setNext(entry);
        length++;
    }
    //尾部删除
    public void endDelete(){
        Entry<E> p;
        if(length == 1) {
            headEntry = null;
            length--;
        }else if(length == 0){
            System.out.println("there is no link now");
        }else{
            for(p = headEntry;p.getNext().getNext() != null;p=p.getNext()){ }
            p.getNext().setValue(null);
            p.setNext(null);
            length--;
        }
    }
    /**
     * 改变节点数据
     * @param arc 原数据值
     * @param aim 目标数据值
     */
    public void changeValue(E arc,E aim){
        if(length != 0) {
            for (Entry<E> p = headEntry; p != null; p = p.getNext()) {
                if (p.getValue().compareTo(arc) == 0) {
                    p.setValue(aim);
                    return;
                }
            }
        }
    }
    //输出倒数第k个节点
    public Entry find(int k){
        if(k<1||k>length)
            return null;
        Entry p1=headEntry;
        Entry p2=headEntry;
        for (int i=0;i<k;i++)
            p2=p2.getNext();
        while (p2!=null) {
            p2=p2.getNext();
            p1=p1.getNext();
        }
        return p1;
    }
    public int getLength() {
        return length;
    }
    //根据数值返回节点
    public Entry<E> getEntry(E value){
        Entry<E> p = headEntry;
        while(p.getNext() != null){
            if(p.getValue().equals(value)){
                return p;
            }
        }
        return null;
    }
    //链表逆置
    public void turnArround(){
        Entry p = headEntry;
        Entry q = headEntry.getNext();
        Entry s = headEntry.getNext().getNext();
        if(length<2){
            return;
        }
        headEntry.setNext(null);
        while(q!= null){
            q.setNext(p);
            p = q;
            q = s;
            if(s!=null){
                s = s.getNext();
            }
        }
        headEntry = p;
    }
    //判断是否有环
    public Entry<E> isRound(){
        Entry fastEntry,slowEntry;//快慢指针
        fastEntry = slowEntry = headEntry;
        while(fastEntry != null || fastEntry.getNext() != null){
            fastEntry = fastEntry.getNext().getNext();
            slowEntry = slowEntry.getNext();
            if(slowEntry == fastEntry){
                return slowEntry;
            }
        }
        return null;
    }
    //找到环的入口
    public Entry<E> findEnter(){
        Entry p,q;
        p = isRound();
        if(p != null){
            q = headEntry;
            while(p != q){
                p = p.getNext();
                q = q.getNext();
            }
            return p;
        }
        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
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
3.主函数类
//单链表测试函数
public class TestDemo<E extends Comparable<E>> {
    /**
     * 找到两个单链表的第一个交点
     * 先统计两个链表长度，让长链表的标记先走差值步，然后两个标记同时行走
     * Math.abs();求绝对值
     * @param a 链表a的头节点
     * @param b 链表b的头节点
     * @return 交点
     */
    public static Entry isIntersect(Link a, Link b){
        int length_1 = a.getLength();
        int length_2 = b.getLength();
        if (length_1 == 0|| length_2 == 0) {
            return null;
        }
        Entry p = a.headEntry;
        Entry q = b.headEntry;
        if(length_1 > length_2){
            for(int i=0;i<length_1-length_2;i++){
                p = p.getNext();
            }
        }else if(length_1 < length_2){
            for(int i=0;i<length_2-length_1;i++){
                q = q.getNext();
            }
        }
        while(p.getNext() != q.getNext()){
            p = p.getNext();
            q = q.getNext();
        }
        return p.getNext();
    }
    //合并有序单链表
    public static Entry mergeLink(Link a,Link b){
        if(a == null && b == null){
            return null;
        }else if(a == null){
            return b.headEntry;
        }else if(b == null){
            return a.headEntry;
        }
        if(a.headEntry == null &&b.headEntry ==null){
            return null;
        }else if(a.headEntry == null){
            return b.headEntry;
        }else if(b.headEntry == null){
            return a.headEntry;
        }
        Entry p1 = a.headEntry;
        Entry p2 = b.headEntry;
        Entry headEntry = p1.getValue().compareTo(p2.getValue()) >0 ? p2:p1;
        Entry p = headEntry;
        while(p1.getNext() != null && p2.getNext() != null){
            if(p == p1){
                p1 = p1.getNext();
            }else{
                p2 = p2.getNext();
            }
            p.setNext((p1.getValue().compareTo(p2.getValue())) >0 ? p2:p1);
            p = p.getNext();
        }
        return headEntry;
    }
    /**
     * 主函数
     * @param args
     */
    public static void main(String[] args) {
        Link<Integer> a = new Link<>();
        Link<Integer> b = new Link<>();
        a.headAdd(9);
        a.headAdd(7);
        a.headAdd(5);
        a.headAdd(3);
        a.headAdd(1);
        b.headAdd(10);
        b.headAdd(8);
        b.headAdd(6);
        b.headAdd(4);
        b.headAdd(2);
        Entry<Integer> e = mergeLink(a,b);
        show(e);
    //打印
    public static void show(Entry headEntry){
        for(Entry p = headEntry;p!=null;p=p.getNext()){
            System.out.print(p.getValue()+" ");
        }
    }
}

  • 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
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

循环单链表

链表类
//循环单链表
public class SingleCircleLink<E extends Comparable<E>>{
    private static class Entry<T extends Comparable<T>>{
        private T value;
        private Entry<T> next;
        private Entry(T value){
            this.value = value;
            this.next = this;
        }
    }
    private Entry<E> headEntry;
    private Entry<E> tailEntry;
    private int count;//节点个数
    //头部增加
    public void addHead(E value){
        Entry<E> entry = new Entry<E>(value);
        if(headEntry == null){
            headEntry = entry;
            tailEntry = entry;
            return;
        }
        entry.next = headEntry;
        tailEntry.next = entry;
        headEntry = entry;
        count++;
    }
    //尾部增加
    public void addTail(E value){
        Entry<E> entry = new Entry<E>(value);
        if(tailEntry == null){
            headEntry = entry;
            tailEntry = entry;
            return;
        }
        tailEntry.next = entry;
        entry.next = headEntry;
        tailEntry = entry;
        count++;
    }
    //删除链表里只有一个节点
    private boolean ifOne(){
        if(count == 1){
            headEntry.value = null;
            headEntry = tailEntry = null;
            count--;
            return true;
        }
        return false;
    }
    //头部删除
    public boolean deleteHead(){
        if(headEntry == null){
            return false;
        }
        if(ifOne()){
            return true;
        }
        tailEntry.next = headEntry.next;
        headEntry.value = null;
        headEntry = headEntry.next;
        count--;
        return true;
    }
    //尾部删除
    public boolean deleteTail(){
        if(tailEntry == null){
            return false;
        }
        if(ifOne()){
            return true;
        }
        Entry<E> e = headEntry;
        for(int i=0;i<count-1;i++){
            e = e.next;
        }
        e.next = headEntry;
        tailEntry.value =null;
        tailEntry = e;
        count--;
        return true;
    }
    //删除指定值节点
    public boolean deleteValue(E value){
        if(count<=0){
            return false;
        }
        Entry<E> e = headEntry;
        if(e.value.compareTo(value)==0){
            headEntry.value = null;
            tailEntry.next = headEntry.next;
            count--;
            return true;
        }
        for(int i=0;i<count;i++){
            if(e.next.value.compareTo(value)==0){
                e.next.value =null;
                e.next = e.next.next;
                count--;
                return true;
            }
            e = e.next;
        }
        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
  • 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
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/777342
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号