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

目录

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