数据结构-链表的简单操作实现

目录

0.链表前序工作

1.构建出一个链表

2.展示链表中的所有存储数据

3.查找关键字key是否在链表中

4.求链表的长度

5.头插法

6.尾插法

7.插入任意位置（规定第一个元素位置为0下标）

8.删除第一次出现的值为key的关键字

9.删除所有值为key的关键字

10.清空所有节点

---

0.链表前序工作

在进行链表的相关操作之前，首先需要进行链表的构造。

在一个链表节点中，有两个区域：

一个用来存储当前节点的数据-val；

另一个需要存储下一个节点的地址。

    static class Node{
        public int val;//存储的数据
        public Node next;//存储下一个节点的地址；
 
        //提供一个构造方法
        public Node(int val){
            this.val = val;
        }
    }

定义一个head，代表当前头节点的引用

public Node head;//代表当前链表头结点的引用

1.构建出一个链表

构建一个链表将构建的链表节点串起来。

这里我们构建四个节点，

 public void createLink(){
        Node node1 = new Node(1);
        Node node2 = new Node(1);
        Node node3 = new Node(1);
        Node node4 = new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
 
    }

2.展示链表中的所有存储数据

将存储在链表中的数据进行展示，这里定义一个节点cur，和head相同的指向。

随后将cur向后挪动，当cur的值不为空的时候，向后挪动打印；

当cur的值为空时，证明链表到达了末尾，已经没有元素，进而跳出while循环。

需要注意的内容：

（1）如果要将整个链表遍历完成 那么就要head == null;
（2）如果是遍历到链表的尾巴。条件是head.next == null；

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

3.查找关键字key是否在链表中

在链表中搜寻是否包含关键字key，

同样我们需要一个新的节点和头节点head指向相同的位置；

向后一直走，循环条件是节点的内容不为null，也就是（cur！=null）

存在结果返回true，否则返回false；

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

4.求链表的长度

链表的长度定义为size（），首先定义变量count等于0，同样定义一个cur节点和head指向相同位置，向后遍历，循环条件为cur != null。每循环一次，计数器数值加1，指针向后挪动一个位置。

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

5.头插法

进行头插法，首先准备好一个新的节点node，用来存放传进来的数据data；

node的next指向head；

让head指向node。

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

6.尾插法

首先判断是否为第一次插入，当头节点为null的时候，将head指向node节点，返回。
如果不是第一次插入节点，同样定义一个为cur的节点指向head；

cur向后挪，直至走到链表最后，将cur的next指向新的节点node，完成尾插操作。

    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;
    }

7.插入任意位置（规定第一个元素位置为0下标）

在链表中插入任意位置，需要传入两个值-位置下标、插入的数值.

判断要插入的位置是否合法：自己写一个方法检查下标：checkIndex

首先，如果插入下标为0下标-头插法；插入下标为链表的长度size-尾插法；

其他情况就是在链表的中间位置：

需要找到链表中需要插入位置的前一个位置的下标位置：findIndexSubOne。【因为我们在这里讨论的链表为单向不带头节点的链表，必须要找到需要元素需要插入位置的前一个位置，进而进行后续操作】。

得到插入到链表中前一个位置的下标，定义为cur；要插入的数据定义为node;

具体两步的指向如下图所示。

    public void addIndex(int index,int data)
            throws ListIndexOutOfException{
        checkIndex(index);
        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;
    }

checkIndex

  private void checkIndex(int index){
        if(index < 0 || index > size()){
            throw new ListIndexOutOfException("index位置不合法！");
        }
    }

ListIndexOutOfException

public class ListIndexOutOfException extends RuntimeException{
    public ListIndexOutOfException() {
    }
 
    public ListIndexOutOfException(String message) {
        super(message);
    }
}

findIndexSubOne

    private Node findIndexSubOne(int index){
        Node cur = head;
        int count = 0;
        while (count != index -1){
            cur = cur.next;
            count++;
        }
        return cur;
    }

8.删除第一次出现的值为key的关键字

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

首先当链表的表头就是我们要找的关键字：将头节点向后挪动，返回即可。

寻找到要删除节点的前一个节点：searchPrev(key)

    public void remove(int key){
        if(head.val == key){
            head = head.next;
            return;
        }
        Node cur = searchPrev(key);//代表当前节点
        if(cur == null){
            return ;
        }
        Node del = cur.next;//代表要删除的节点
        cur.next = del.next;
    }

searchPrev(key)

    private Node searchPrev(int key){
        if(head == null){
            return null;//一个节点都没有
        }
        Node cur = head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        //代表根本没有要删除的节点
        return null;
    }

9.删除所有值为key的关键字

在链表中删除所有值为key的关键字

首先判断链表中有无元素，如果头节点的指向为null的话，返回return;

在这里定义两个指针prev指向头的位置；

cur指向头的下一个位置。

这里选择先不进行对头结点的判定

    public void removeAllKey(int key){
        if(head == null){
            return;
        }
        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;
        }
    }

10.清空所有节点

 public void clear(){
        head = null;
    }