认识链表以及其常见操作Java代码实现

admin • 2021-12-20 20:09 • Java

认识链表以及其常见操作

1.链表的概念及其结构
- 1.1链表的概念
- 1.2链表的结构和种类
2.链表的实现

1.链表的概念及其结构

1.1链表的概念

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

链表的每个节点都是有数据域和指针域组成。
指针域用来储存数据，指针域用来指向下一个节点。

如下图所示

1.2链表的结构和种类

链表主要分为三类：

带头和不带头
单向和双向
循环和非循环

这三类可以演化出8种结构：
单向：
单向带头循环
单向带头非循环
单向不带头循环
单向不带头非循环
双向：
双向带头循环
双向带头非循环
双向不带头循环
双向不带头非循环

本篇博客重点是单向不带头非循环

带头和不带头的区别：
带头：这个链表的头结点随时可能发生改变
不带头：这个链表的头结点不在发生改变

常见链表示意图：
无头单向链表

有头单向链表：

循环单链表：

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

2.链表的实现

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

class ListNode{
    public int val;//数据域
    public ListNode next;//null   指针域

    public ListNode(int val){
        this.val=val;
    }
}
public class MyLinkedList {
    public ListNode head;//标识单链表的头节点
    //采用穷举的方式创建链表，只是为了方便理解
   public void createList(){
       //对每一个节点进行赋值
       ListNode listNode1 = new ListNode(1);
       ListNode listNode2 = new ListNode(2);
       ListNode listNode3 = new ListNode(3);
       ListNode listNode4 = new ListNode(4);
       //将节点之间链接起来
       listNode1.next = listNode2;
       listNode2.next = listNode3;
       listNode3.next = listNode4;
       this.head = listNode1;//指明头节点
   }

2.1.1准备方法

2.1.1.1打印单链表

   //打印单链表
    public void show(){
        ListNode cur = this.head;//防止在打印的过程中导致头节点位置偏移
        while(cur!=null){//不是空节点
            System.out.println(cur.val+" ");
            cur=cur.next;//指向节点向后移动一位
        }
        System.out.println();
    }

2.1.1.2得到链表的长度

//得到链表的长度
    public int size(){
        ListNode cur = this.head;
        int count = 0;//统计链表的长度
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

2.1.1.3查找是否包含关键自key在单链表中

//查找是否包含关键自key在单链表中
    public boolean contains(int val){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val==val){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

2.1.1.4查找具有指定值的前一个节点

//查找具有指定值的前一个节点
    public ListNode searchPrevNode(int val){
        ListNode cur = this.head;
        while(cur.next!=null){
            if(cur.next.val == val){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

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

//查找是否包含关键自key在单链表中
    public boolean contains(int val){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val==val){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

2.1.2头插法

    //头插法
    public void addFirst(int data){
        ListNode listNode = new ListNode(data);
        if(this.head == null){//判断是否为第一次插入
            this.head = listNode;
        }else{
            listNode.next = this.head;//先绑定后一个节点
            this.head = listNode;//更新头节点位置
        }
    }

2.1.3尾插法

//尾插法
    public void addLast(int data){
        ListNode listNode = new ListNode(data);
        if(this.head == null){//判断是否为第一次插入
            this.head = listNode;
        }else{
            ListNode cur = this.head;//防止头节点位置偏移
            while(cur.next!=null){
                cur = cur.next;//找到尾节点
            }
            cur.next = listNode;//链接节点
        }
    }

2.1.4任意位置插入，假设第一个数据节点为0下标

 //任意位置插入，第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index < 0 || index > size()){//首先判断坐标是否合法
            System.out.println("下标不合法");
            return;
        }
        //若插入位置为第一个位置，头插法
        if(index == 0){
            addFirst(data);
            return;
        }
        //若插入位置为最后一个位置，尾插法
        if(index == size()){
            addLast(data);
            return;
        }
        ListNode cur = searchPrev(index);//找到指定的坐标位置
        ListNode listNode = new ListNode(data);
        //插入节点
        listNode.next = cur.next;
        cur.next = listNode;
    }

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

删除某一个节点的原理就是不再有引用指向该节点，Java虚拟机会自动回收

    //删除第一次出现关键字key的节点
    public void remove(int val){
        if(this.head ==null) return;//没有节点直接返回
        //单独判断头节点的问题
        if(this.head.val == val){
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrevNode(val);//查找到指定值的坐标位置的前一个节点
        if(cur ==null){//判断坐标是否为空
            System.out.println("没有你要删除的节点");
            return;
        }//删除该节点
        ListNode del = cur.next;
        cur.next = del.next;
    }

2.1.6删除所有值为key的节点

 //删除所有值为key的节点
    public void removeAllKey(int val){
        if(this.head == null){//若没有节点，直接返回
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while(cur!=null){//节点不为空，进入循环
            if(cur.val == val){//找到一个与指定值相同的节点，删除
                prev.next = cur.next;
                cur = cur.next;//删除后向后移动一位
            }else{//与指定值不同，向后移动一位
                prev = cur;
                cur = cur.next;
            }
        }
        //最后判断头节点是否为该值
        if(this.head.val == val){
            this.head = this.head.next;

        }
    }

2.2无头双向链表实现

class ListNodeD{
    public int data;//数据域
    public ListNodeD prev;//前驱
    public ListNodeD next;//后继

    public ListNodeD(int data){
        this.data = data;
    }
}

public class MyRealLinkedList {
    public ListNodeD head;//头
    public ListNodeD last;//尾

    public MyRealLinkedList(){
        //this.head = new ListNode(-1);傀儡节点
    }

2.2.1准备方法

2.2.1.1查找节点

    //查找节点
    public ListNodeD findIndex(int index){
        ListNodeD cur = this.head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

2.2.1.2得到链表的长度

    //得到链表的长度
    public int size(){
        int count = 0;
        if(this.head == null) return count;//链表长度为零
        ListNodeD cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

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

    //查找是否包含关键字key在链表中
    public boolean contains(int key){
        if(this.head == null) return false;
        ListNodeD cur = this.head;
        while(cur!=null){
            if(cur.data == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

2.2.1头插法

   //头插法
    public void addFirst(int data){
        ListNodeD node = new ListNodeD(data);
        if(head == null){
            this.head = node;
        }else{
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

2.2.2尾插法

    //尾插法
    public void addLast(int data){
        ListNodeD node = new ListNodeD(data);
        if(head == null){
            this.head = node;
            this.last = node;
        }else{
            last.next = node;
            node.prev = last;
            last = node;

        }
    }

2.2.3任意位置插入，假设第一个数据节点为0下标

   //任意位置插入，第一个节点为0下标
    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;
        }
        ListNodeD cur = findIndex(index);
        ListNodeD node = new ListNodeD(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur;
        cur.prev = node;
    }

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

   //删除第一次出现key的节点
    public void remove(int key){
        ListNodeD cur = this.head;
        while(cur!=null){
            if(cur.data == key){
                //判断是不是头节点
                if(cur == this.head){
                    this.head = this.head.next;
                    if(this.head == null){//防止只有一个节点
                        this.last = null;
                    }else{
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    //尾巴节点
                    if(cur.next == null){
                        this.last = cur.prev;
                    }else{
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur = cur.next;
            }
        }
    }

2.2.5删除所有值为key的节点

    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNodeD cur = this.head;
        while(cur!=null){
            if(cur.data == key){
                //判断是不是头节点
                if(cur == this.head){
                    this.head = this.head.next;
                    if(this.head == null){//防止只有1个节点
                        this.last = null;
                    }else{
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    //尾巴节点
                    if(cur.next == null){
                        this.last = cur.prev;
                    }else{
                        cur.next.prev = cur.prev;
                    }
                }
                cur = cur.next;//继续往后走，直到null的时候
            }else{
                cur = cur.next;
            }
        }
    }

2.2.6清空链表

   //
    public void clear(){
        ListNodeD cur = this.head;
        while(cur != null){
            ListNodeD curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;
        this.last = null;
    }

}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

java 数据结构链表

二维码

LeetCode – 997 -找到小镇的法官 – Java

< <上一篇

C++与Java共同点

下一篇>>

搜索内容