【数据结构】LinkedList与链表

xxxflower

发布于 2023-04-16 17:45:28

2900

发布于 2023-04-16 17:45:28

?1.ArrayList的缺陷

ArrayList的底层是一段连续空间的数组，在ArrayList位置任意位置插入或者删除元素时，就需要将后续元素整体往前或者往后移动，时间复杂度为O(n)，效率较低。所以ArrayList不适合做任意位置插入和删除比较多的场景。因此，java集合中又引入了LinkList，即链表结构。

?2.链表

2.1链表的概念及结构

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

注意：

由上图可得，链式结构在逻辑上是连续的，但是在物理上不一定连续。如图：

现实中的节点一般都是从堆上申请出来的。
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。实际中链表的结构非常多样：

我们需要重点学习的有：

单向非循环无头结点链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

无头双向链表

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

2.2链表的模拟实现

MySingleList

使用内部类定义一个节点类。

打印链表： 1.为了保证head的值不变，定义一个cur 当cur != null(循环条件)时走完整个链表。 2.打印cur.val 3.cur = cur.next.

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

如何得到链表的长度？ 1.定义一个计数器count 2.当cur！=null时count++； 3.cur = cue.next;

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

头插法： 1.根据形参的数据创建一个节点 2.node.next = this.head; head = node;

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

尾插法： 1…根据形参的数据创建一个节点node 1.找到尾部。定义一个cur。cur = this.head; 当cur.next == null时，即找到了尾部。 3.判断链表是否为空 4.将节点的node给尾部的next

 public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if(cur == null){
            this.head = node;
        }else{
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

任意位置插入,第一个数据节点为0号下标：首先判断index位置是否合法。分三种情况，头插，尾插和中间插入 1.走index-1步，找到cur 2.ListNode node = new ListNode(); node.next = cur.next;1?? cur.next = node;2??

//任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index < 0 || index > this.size()){
            System.out.println("index位置不合法！");
            throw new IndexWrongfulExpection("index位置不合法！");
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index ==this.size()){
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        while(index-1 != 0){
            cur = cur.next;
            index--;
        }
        node.next = cur.next;
        cur.next = node;
    }

查找是否包含关键字key是否在单链表当中： 1.判断链表是否为空？ 2.写一个循环遍历数组找到cur.val == key

 public boolean contains(int key){
        if(this.head == null){
            System.out.println("链表为空！");
            return false;
        }
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

删除第一次出现关键字为key的节点 1.判断链表是否为空？？ 2.如果删除的是头结点？？ 3.写一个函数，封装起来，用于查找key的index的前一个值 4.删除

public void remove(int key){
        if(this.head == null){
            System.out.println("链表为空！");
            return;
        }
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = findPrevOfKey(key);
        if(cur == null){
            System.out.println("没有你要删除的数字！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    private ListNode findPrevOfKey(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if(cur.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

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

链表是否为空？？
如何删除？定义一个cur = head.next;再定义一个prev作为cur的前驱。
遍历链表。如果cur.val == key；prev.next = cur.next; cur = cur.next;
如果cur != key;prev = cur;cur = cur.next;
以上的方法不能解决头结点是key的情况，所以在需要判断一下头结点位key的情况下做以处理？

//删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head == null){
            System.out.println("链表为空！");
            return;
        }
        ListNode cur = this.head.next;
        ListNode prev = head;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){
            this.head = this.head.next;
        }
    }

到这里我们对单链表就有一定的认识啦~

?3.LinkedList

如图，为双向无头循环链表下面我们以此为例来实现双链表的操作。

3.1LinkedList的模拟实现

MyLinkedList

首先使用内部类创建一个ListNode：

static class ListNode{
        public int val;
        public ListNode prve;
        public ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }

头插法：

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

        }
    }

尾插法：

//尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }
        node.prve = tail;
        tail.next = node;
        tail = node;
    }

任意位置插入,第一个数据节点为0号下标

  //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        //1.判断index位置的合法性
        if(index < 0 || index > size()){
            System.out.println("index位置不合法！");
            throw new IndexWrongfulExpection("index位置不合法！");
        }
        //2.判断特殊位置
        if(index == 0){
            addFirst(data);
            return ;
        }
        if(index == size()){
            addLast(data);
            return ;
        }
        //3.找到index位置节点的地址
        ListNode node = new ListNode(data);
        ListNode cur = findIndexListNode(index);
        //4.修改指向
        node.next = cur;
        node.prve = cur.prve;
        cur.prve.next = node;
        cur.prve = node;

    }
    public ListNode findIndexListNode(int index){
        ListNode cur = this.head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

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

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

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

public void remove(int key){
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                if(cur == head){
                    head = head.next;
                    if(head != null){
                        head.prve = null;
                    }else{
                        tail = null;
                    }
                }else{
                    cur.prve.next = cur.next;
                    if( cur.next != null){
                        cur.next.prve = cur.prve;
                    }else{
                        this.tail = cur.prve;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

删除所有值为key的节点：此处和删除首个关键字值的代码大同小异。只需要遍历完整个链表即可。

  //删除所有值为key的节点
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                if(cur == head){
                    head = head.next;
                    if(head != null){
                        head.prve = null;
                    }else{
                        tail = null;
                    }
                }else{
                    cur.prve.next = cur.next;
                    if( cur.next != null){
                        cur.next.prve = cur.prve;
                    }else{
                        this.tail = cur.prve;
                    }
                }
            }
            cur = cur.next;
        }
    }

双链表和单链表的部分函数写法思路是一样的。