顺序表——单向无头链表基础实现

目录

理解单链表

什么是单链表

什么是头节点（head）

如何创建节点

如何找到每一个节点

找到某个索引节点

遍历整个链表： 

创建实现类 （增删改查）

代码实现

增

头插法

任意位置插入

尾插法

查

判断index合法性

查询第一个值为val的节点

查询是否包含指定值的节点

查询索引index位置的值

改

修改索引index的值为newVal，并返回旧值oldVal。

删

删除index位置的元素

删除第一个值为val的节点

 删除所有值为val的节点

---

理解单链表 什么是单链表

单链表也是顺序表的一种，但是和数组不一样，单链表在物理上是不连续的，只有逻辑上连续。

单链表是由无数个节点连接到一起的，每个节点存放一个节点值val和下一个节点的地址next

我们可以把单链表想成一列火车，每一个节点就是一节车厢。而火车，必然会有车头和车尾。

无头单链表则是我今天要说的重点内容。

无头单链表指：没有单独的无val值节点存放head

什么是头节点（head）

单链表的车头部分，驱动整个单链表能够运作起来，为重中之重。

如何创建节点

我们之前说，节点需要存放值和地址，所以我们可以创建一个类来存放这两个值。

class Node {
    int val;
    Node next;//存放下一个节点的地址，所以采用Node类定义
}

如何找到每一个节点

遍历链表，用来找到每一个节点。

找到某个索引节点

用于找节点或者节点前驱

Node prev= head;
        for (int i = 0; i < index-1; i++) {
            prev=prev.next;
        }

遍历整个链表： 

用于找到某个节点值为val的索引

for (Node x = head; x != null; x=x.next)

创建实现类 （增删改查）

一个头节点head  和 节点个数size

因为用户不需要关注这些值所以我们封装起来

public class SingleLinkerList {
    private Node head;
    private int size;
 }

代码实现 增 头插法

在链表最前方插入节点，并作为头节点。

我们需要判断目前链表是否为空，如果为空则是第一次插入节点。

否则便是更换头节点。

public void addFirst(int val) {
        Node newNode = new Node();
        newNode.val = val;
        if (head != null) {
            newNode.next = head;
        }
        head=newNode;
        size++;
    }

任意位置插入

需要插入位置索引index 和 插入的值val

我们需要找到index的前驱index-1

不懂就自己画个图

 同时，我们需要判断index是否合法，不可以在size以外的值插入

另外，如果index为0我们可以直接引用头插入方法，而且头插入方法还包含第一次插入的情况，一举两得。

 public void addIndex(int index,int val) {
        if(index<0||index>size){
            System.err.println("illegal index!!");
            return;
        }
        if(index==0) {
            addFirst(val);
        } else {
            Node prev = head;
            Node newNode=new Node();
            newNode.val=val;
            for (int i = 0; i < index-1; i++) {
                prev=prev.next;
            }
            newNode.next=prev.next;
            prev.next=newNode;
            size++;
        }
    }

尾插法

属于特殊的任意位置插入，也就是size位置插入

直接调用任意位置插入方法即可。

查

前文提到，想查到某个节点可以遍历链表，所以以下几种查询均可遍历链表。

判断index合法性

我们不妨把判断index合法性写成一个私有方法，因为总要用。

public boolean rangerCheck(int index) {
        if(index<0||index>=size) {
            return false;
        }
        return true;
    }

查询第一个值为val的节点

public int getByValue(int val) {
        int index=0;
        for (Node x = head; x != null; x=x.next) {
            if(x.val==val) {
                return index;
            }
            index++;
        }
        return -1;
    }

查询是否包含指定值的节点

调用上个方法即可

public boolean contains(int val) {
        return getByValue(val)!=-1;
    }

查询索引index位置的值

public  int get (int index) {
       if(rangerCheck(index)==false) {
           System.err.println("illegal index!!!");
           return -1;
       }
       Node prev = head;
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        return prev.val;
    }

改 修改索引index的值为newVal，并返回旧值oldVal。

public int set(int index,int newVal) {
        if(rangerCheck(index)==false) {
            System.err.println("illegal index");
            return -1;
        }
        Node prev = head;
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        int oldVal = prev.val;
        prev.val=newVal;
        return oldVal;
    }

删

删中最重要的思想就是找前驱，利用前驱

删除index位置的元素

同样先判断合法性，然后通过更改前驱的连接点，让需要删除的节点断开，并且可以让断开的节点指向空地址彻底扔掉此节点。还要判断是否删除的是头节点。

public int remove(int index) {
        if(rangerCheck(index)==false) {
            System.err.println("illegal index!!");
            return -1;
        }
        if(index==0) {
            Node x=head;
            head=head.next;
            x.next=null;
            size--;
            return x.val;
        }
        Node prev= head;
        for (int i = 0; i < index-1; i++) {
            prev=prev.next;
        }
        Node node = prev.next;
        prev.next=node.next;
        node.next=null;
        size--;
        return node.val;
    }

删除第一个值为val的节点

首先我们需要判断，头节点是否需要删除，若需要删除，则直接换头返回。

然后，我们还需判断头节点是否为空，如果头节点为空，那么直接返回即可。

注意：在此方法中，两个情况的先后顺序不做要求，因为无论哪种情况我们都会直接返回，但是为了方便下一个方法的使用我们把头节点删除放在了前面，不然按照逻辑，我认为把判断头节点为空放在前面比较好。

如果两种情况均未发生，我们遍历整个链表找需要删除节点的前驱，注意我们需要找的是前驱，所以不可以直接遍历到最后一个节点，而是最后一个节点之前。

 public void removeValueOnce(int val) {
        if(head.val == val ) {
            Node x = head;
            head = x.next;
            size--;
            x.next=null;
            return;
        }
        if(head==null) {
            System.err.println("Null List");
            return;
        }
        Node prev = head;
        while(prev.next!=null) {
            if(prev.next.val == val) {
                Node node = prev.next;
                prev.next = node.next;
                node.next = null;
                size--;
                return;
            }
            prev= prev.next;
        }
    }

 删除所有值为val的节点

首先我们判断头节点是否为待删除节点，删除头节点直到找到一个非待删除节点作为头节点。

然后通过遍历，依次改变节点前驱位置，并删除需要删除的节点。

注意点1：先判断头节点是否为待删除节点，并使用while循环，如果全部是待删除节点，为避免越界情况出现，我们还需要保证头节点不是null才可以进行删除。

注意点2：无论是开始的头节点就为空，还是删除后把节点删完了，遇到头节点已经为空的情况，我们都需要直接结束方法，以免向下进行时出现越界。

注意点3：在找到头节点并开始遍历删除后，我们每删除一个节点，不可改变节点前驱的位置，知道找到下一个未删除节点，再改变节点前驱。

因此我们写出代码：

public  void removeAllValue(int val) {
        while(head!=null && head.val==val) {
            //头节点需要删除
            Node x = head;
            head = x.next;
            x.next = null;
            size--;
        }
        //头节点已经不需要删除，判断头节点是否为空
        if(head==null) {
            System.err.println("Null List");
            return;
        }
        else {
            Node prev = head;
            //保证要删除节点的前驱的值不是val
            while (prev.next != null) {
                //至少还有后继节点
                if (prev.next.val == val) {
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size--;
                } else {
                    prev = prev.next;
                }
            }
        }
    }