实现无头单链表的基本操作

痛定思痛。 2023-09-27 13:46 109阅读 0赞

## 无头指针的单链表的结构 ##

![e818f8062cd44df58f0f9335fabcd539.png][]

## 创建一个节点类，一个初始链表 ##

static class Node {
            public int val;//存储的数据
            public Node next;//存储下一个节点的地址
    
            public Node (int val) {
                this.val = val;
            }
        }
    
        public Node head;// 代表当前链表的头节点的引用
    
    //初始单链表
        public void createLink() {
            Node node1 = new Node(12);
            Node node2 = new Node(45);
            Node node3 = new Node(23);
            Node node4 = new Node(90);
            node1.next = node2;
            node2.next = node3;
            node3.next = node4; /* */
            head = node1;
        }

## 打印链表，遍历链表 ##

> Node cur = head; 的作用是为了实现“滴滴代跑”，防止遍历一遍以后head==null找不到头结点了。
> 
> 过程：设置一个cur，代替head
> 
> 用循环去遍历数组，循环条件，cur不为空

public void display() {
            Node cur = head;
    
            //如果说 把整个链表 遍历完成 那么 就需要 head == null
            // 如果说 你遍历到链表的尾巴  head.next == null
            
            while (cur != null) {
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }

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

> 过程：
> 
> 1.用循环去遍历数组，循环条件，cur不为空
> 
> 2.用if去判断 链表元素是否等于关键字

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

## 得到单链表的长度 ，时间复杂度O(N) ##

> 过程：
> 
> 1.用循环去遍历数组，循环条件，cur不为空
> 
> 2.用count在循环中计数

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

## 头插法插入数据，时间复杂度 O(1) ##

> 过程：
> 
> 1.创建一个新的结点
> 
> 2.把head连接在新节点后面
> 
> 3.新节点成为新的head

![2a1ae55126b6444581719563d6c8f998.png][]

public void addFirst(int data){
            Node node = new Node(data);
            node.next = head;
            head = node;
        }

## 尾插法插入数据，时间复杂度 O(N) ##

> 过程：
> 
> 1.创建新节点
> 
> 2.判断表是否为空，如果是，插入的元素就是表头
> 
> 3.查找最后一个元素，用循环去遍历数组，循环条件，cur的下一个不为空
> 
> 4.找到以后将node作为cur的下一个

![60dc2b854eb7422483f4cf68cd78756c.png][]

public void addLast(int data){
            Node node = new Node(data);
    //判断此链表是否为空表，如果是，插入的元素就是表头
            if(head == null) {
                head = node;
                return;
            }
            Node cur = head;
    //找链表的最后一个元素
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }

## 任意位置插入 ##

> 1.判断位置是否合法  
> 2.实现插入位置为0用头插法，插入位置在最后用尾插法  
> 3.寻找插入位置，（需要找到index的前一个）实现查找插入位置的方法：用count计数，用循环判断cur的值是否是需要的值  
> 4.实现插入
> 
> 注：因为插入的语法 node.next = cur.next; cur.next = node;（看图示），所以查找插入位置时需要找到index的前一位

![bc31874fb47349749739945e2a3a6c8a.png][]

public void addIndex(int index,int data)
                throws ListIndexOutOfException{
    //判断插入位置的下标是否合法，不合法抛出异常
            checkIndex(index);
    //插入位置为0，直接用头插法
            if(index == 0) {
                addFirst(data);
                return;
            }
    //插入位置在最后，直接用尾插法
            if(index == size()) {
                addLast(data);
                return;
            }
    
    //找到插入的位置，进行插入
            Node cur = findIndexSubOne(index);
            Node node = new Node(data);
            node.next = cur.next;
            cur.next = node;
        }
    
    //查找插入位置的方法
    private Node findIndexSubOne(int index) {
            Node cur = head;
            int count = 0;
            while (count != index-1) {   // 需要找到插入位置的前一位
                cur = cur.next;
                count++;      
            }
            return cur;
        }
    
    //判断位置合不合法的方法
        private void checkIndex(int index) throws ListIndexOutOfException{
            if(index < 0 || index > size()) {
                throw new ListIndexOutOfException("index位置不合法");
            }
        }

##  ##

## 删除第一次出现关键字为key的节点，时间复杂度 O(N) ##

![83be4940468444a4b5cb167800cd18e7.png][]

public void remove(int key){
    
            if(head == null) {
                return ;//一个节点都没有
            }
            if(head.val == key) {
                head = head.next;    //头结点的值就是要找的值
                return;
            }
            Node cur = searchPrev(key);  //key的前一个节点
            if(cur == null) {
                return;
            }
            Node del = cur.next;//要删除的节点
            cur.next = del.next;
        }
        /*
     找到关键字key的前一个节点的方法
         */
        private Node searchPrev(int key) {
            Node cur = head;
            while (cur.next != null) {
                if(cur.next.val == key) {
                    return cur;
                }
                cur = cur.next;
            }
            return null;//没有你要删除的节点
        }

## 删除所有值为key的节点 ##

> 用双指针，两个指针，pre,cur,pre在处cur后面（看图）  
> 1.判断链表是否为空  
> 2.创建两个指针  
> 3.用循环查找key，分两种情况移动指针  
> 4.判断head的值是否为key

![613cd20656814e5daf7c071d87f8f742.png][]

//用双指针的方法
    
    public void removeAllKey(int key){
            if(head == null) {
                return;
            }
            /*while(head.val == key) {
                head = head.next;
            }*/
            Node prev = head;
            Node cur = head.next;
            while (cur != null) {
                if(cur.val == key) {
                    prev.next = cur.next;
                    cur = cur.next;
                }else {
                    prev = cur;
                    cur = cur.next;
                }
            }
            if(head.val == key) {
                head = head.next;
            }
        }

## 清空链表的内容（保证链表当中所有的节点都可以被回收） ##

public void clear() {
    //直接把头结点置为空
            head = null;
        }

[e818f8062cd44df58f0f9335fabcd539.png]: https://img-blog.csdnimg.cn/e818f8062cd44df58f0f9335fabcd539.png
[2a1ae55126b6444581719563d6c8f998.png]: https://img-blog.csdnimg.cn/2a1ae55126b6444581719563d6c8f998.png
[60dc2b854eb7422483f4cf68cd78756c.png]: https://img-blog.csdnimg.cn/60dc2b854eb7422483f4cf68cd78756c.png
[bc31874fb47349749739945e2a3a6c8a.png]: https://img-blog.csdnimg.cn/bc31874fb47349749739945e2a3a6c8a.png
[83be4940468444a4b5cb167800cd18e7.png]: https://img-blog.csdnimg.cn/83be4940468444a4b5cb167800cd18e7.png
[613cd20656814e5daf7c071d87f8f742.png]: https://img-blog.csdnimg.cn/613cd20656814e5daf7c071d87f8f742.png