数据结构-单链表（Java实现，通俗易懂）

亦凉 2023-09-27 13:09 126阅读 0赞

**目录**

单链表的结构

链表的基本操作（非常多）

--------------------

## 单链表的结构 ##

**单链表**是一种链式存取的 数据结构 ，用一组地址任意的 存储单元 存放线性表中的数据元素。 链表中的数据是以结点来表示的，每个结点的构成：元素 + 指针 (指示后继元素 存储 位置)，元素就是存储数据的存储单元，指针就是连接每个结点的 地址 数据。

![3989081d8cfb4847849b412aacfb93c7.png][]

用图形来表示链表就如上图，像不连续的空间连起来了一样。

因为不带头单链表使用较多，所以我们本章只实现此链表

链表类：

public class LinkList {
        private Node head; 保存链表头节点
        private int size;  保存链表节点长度
        链表类
        static class Node{ 
            public int val;     链表值
            public Node next;   保存下一个节点的地址
    
            public Node(){
    
            }
    
            public Node(int val) {
                this.val = val;
            }
        }
    
    
        public LinkList() {  链表初始化
            this.head = null;
            this.size = 0;
        }
    
    }

## 链表的基本操作（非常多） ##

头插法

public void addFront(int val){
            Node newNode=new Node(val);
            if (head==null){   如果head为null，说明没有结点，所以让head指向新结点
                head=newNode;
                return;
            }
            newNode.next=head;
            head=newNode;
            size++;     链表长度+1
        }

尾插法

public void addLast(int val){
            Node newNode=new Node(val);
            if (head==null){
                head=newNode;
                return;
            }
            Node cur=head;
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=newNode;
        }

在指定位置上插入结点

public void addN(int n,int data){
            if (n>size||n<=0){
                System.out.println("n不合法");
                return;
            }
            Node newNode=new Node(data);
            if (head!=null) {
                int count=1;
                Node cur=head;
                找到n位置的前驱节点
                while (count<n-1){
                    cur=cur.next;
                    count++;
                }
                插入结点
                newNode.next=cur.next;
                cur.next=newNode;
            }else {
                n合法且当head为空的时候，head直接指向新节点
                head=newNode;
            }
        }

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

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

删除所有值为key的节点

public void removeAllKey(ListNode head,int key){
        if (head==null){
            return;
        }
        ListNode p=head;
        ListNode q=p.next;
        while (q!=null){
            if (q.val==key){
                p.next=q.next;
                size--;
            }else {
                p = q;
            }
            q = p.next;
        }
        if (head.val==key){
            head=head.next;
            size--;
        }
    }

修改值为key的全部结点

public void change(int val,int key){
            if (head==null){
                System.out.println("没有此结点");
                return;
            }
            Node cur=head;
            while (cur!=null){
                if (cur.val==val){
                    cur.val=key;
                }
                cur=cur.next;
            }
        }

修改第n个的值为key

public void changeN(int n,int key){
            判断n的合法性
            if (n>size||n<=0){
                System.out.println("n不合法");
                return;
            }
            if (head!=null) {
                int count=1;
                Node cur=head;
                找到链表中n结点
                while (count<n){
                    cur=cur.next;
                    count++;
                }
                cur.val=n;
            }else {
                System.out.println("没有结点");
            }
        }

查找链表中第一次出现为key的结点

public Node findKey(int key){
            if (head!=null) {
                Node cur=head;
                查找结点值为key的结点
                while (cur!=null){
                    找到返回cur
                    if (cur.val==key){
                        return cur;
                    }
                    cur=cur.next;
                }
    
            }else {
                System.out.println("没有结点");
            }
            最后没有找到，返回空
            return null;
        }

查找链表中n位置的结点

和上面的的修改原理一样，这里不过多赘述

public Node findN(int n){
            if (n>size||n<=0){
                System.out.println("无效位置");
                return null;
            }
            if (head!=null) {
                int count=1;
                Node cur=head;
                while (count<n){
                    cur=cur.next;
                    count++;
                }
                return cur;
            }else {
                System.out.println("没有结点");
                return null;
            }
        }

判断链表是否包含某一元素

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

获取链表长度

public int size(){
            return size;
        }

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

遍历链表

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

清空链表

public void clear(Node head){
        head=null;
    }

public void clear(){
            //this.head = null;//这种做法 比较粗暴！
            Node cur = this.head;
            Node curNext = null;
            while (cur != null) {
                curNext = cur.next;
                cur.next = null;
                cur = curNext;
            }
            head = null;
        }

好了，本期内容就到这里，关注我，我和我的动物朋友会非常开心，下期会给大家带来一些链表的oj题

[3989081d8cfb4847849b412aacfb93c7.png]: https://img-blog.csdnimg.cn/3989081d8cfb4847849b412aacfb93c7.png