[4] 实现无头单向非循环链表

目录

一、框架

二、实现各个方法

三、测试各个方法

四、源码

一、框架

一个单向链表的节点，有数值域和下一个节点的地址

我们可以设计一个链表类，在这个链表类设计一个节点内部类，这里设计成内部类的形式，因为链表是由节点组成的，所以可以设计成内部类

public class MySingleList {static class ListNode{//链表是由节点组成的，所以可以设计成内部类public int val;//数值域public  ListNode next;//存储下一个节点的地址public ListNode(int val) {this.val = val;}}public ListNode head;
}

二、实现各个方法

（1）手动创建链表

    public void createList(){ //手动创建链表ListNode listNode1 = new ListNode(12);ListNode listNode2 = new ListNode(23);ListNode listNode3 = new ListNode(34);ListNode listNode4 = new ListNode(45);ListNode listNode5 = new ListNode(56);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;head = listNode1;}

（2）得到单链表的长度

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

（3）遍历链表

    //遍历链表public void display(){ListNode cur = head; //不用head去遍历，这样head就不会移动while (cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}

 （4）头插法

    //头插法public void addFirst(int data){ListNode node = new ListNode(data);//分析可知可以不用判断链表是否为空
//        if(head == null){
//            head = node;
//        }node.next = head;head = node;}

 （5）尾插法

    //尾插法//需要判断head是否为空，不然cur = head，然后cur.next = node，会发生空指针异常public void addLast(int data){ListNode node = new ListNode(data);if(head == null){head = node;}else {ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = node;}}

  (6)任意一个位置插入，设第一个数据节点为0号下标

    //任意一个位置插入，设第一个数据节点为0号下标public void addIndex(int index,int data){ListNode node = new ListNode(data);if(index<0 || index>size()){return;}if(index == 0){addFirst(data);}if(index == size()){addLast(data);}ListNode cur = findNode(index);node.next = cur.next;cur.next = node;}private ListNode findNode(int index){int count = 0;ListNode cur = head;while (count != index-1){cur = cur.next;count++;}return cur;}

（7）查找关键字key是否在单链表中

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

（8)删除第一次出现关键字为key的节点

    //删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;while (head == null){System.out.println("此时链表为空，不能进行删除");return;}if(head.val == key){//判断第一个节点是否为要删除的节点head = head.next;return;}while (cur.next != null){if(cur.next.val == key){cur.next = cur.next.next;return;}cur = cur.next;}if(cur.next == null){System.out.println("链表中不存在所要删除的节点");return;}}

（9）删除所有值为key的节点

//删除所有值为key的节点public void removeAllKey(int key){if(head==null){return;}ListNode prev = head;ListNode 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() {//粗暴的做法//this.head = null;//一个一个置为空ListNode cur = head;ListNode curNext = null;while (cur != null){curNext = cur.next;cur.next = null;cur = curNext;}head = null;}

三、测试各个方法

public class Test {public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.createList();System.out.println("=====================");mySingleList.addFirst(1);mySingleList.display();System.out.println("=====================");mySingleList.addLast(45);mySingleList.display();System.out.println("=====================");boolean ret = mySingleList.contains(45);if(ret){System.out.println("存在这个数");}else {System.out.println("不存在这个数");}System.out.println("=====================");mySingleList.addIndex(2,166);mySingleList.display();System.out.println("=====================");mySingleList.remove(2);mySingleList.display();System.out.println("=====================");mySingleList.removeAllKey(45);mySingleList.display();System.out.println("=====================");mySingleList.clear();mySingleList.display();}

四、源码

_20230411/src · benxiangsj/java learning - 码云 - 开源中国 (gitee.com)https://gitee.com/benxiangsj/java-learning/tree/22866b8267171ace6977145ab6dee23b4f3769ef/_20230411/src