图解数据结构——链表（一）

一、链表的概念

💡链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的.

二、接口实现

设置节点

classListNode{publicint val;publicListNode next;publicListNode(int val){this.val = val;}}

（1）头插法

图解：

代码实现：

//头插法publicvoidaddFirst(int data){ListNode node =newListNode(data);if(this.head ==null){this.head = node;}else{
            node.next =this.head;this.head = node;}}

（2）尾插法

图解：

代码实现：

//尾插法publicvoidaddLast(int data){ListNode node =newListNode(data);if(null==this.head){this.head = node;}else{ListNode cur =this.head;while(cur.next !=null){
                cur = cur.next;}//cur == null
            cur.next = node;}}

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

图解：

代码实现：

//找到index-1位置的地址publicListNodefindIndex(int index){ListNode cur =this.head;while(index-1!=0){
            cur = cur.next;
            index--;}return cur;}publicvoidaddIndex(int index,int data){ListNode node =newListNode(data);if(index <0|| index >size()){System.out.println("小标错误");return;}if(0== index){addFirst(data);return;}if(size()== index){addFirst(data);return;}//中间插ListNode cur =findIndex(index);
       node.next = cur.next;
       cur.next = node;}

（4）打印

图解：

代码实现：

//打印publicvoiddisplay(){ListNode cur =this.head;while(cur !=null){System.out.print(cur.val+" ");
            cur = cur.next;}System.out.println();}

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

图解：

代码实现：

//查找是否包含关键字key是否在单链表当中publicbooleancontains(int key){ListNode cur =this.head;while(cur !=null){if(cur.val == key){returntrue;}
            cur = cur.next;}returnfalse;}

（6）得到单链表的长度

图解：

代码实现：

//得到单链表的长度publicintsize(){int count =0;ListNode cur =this.head;while(cur !=null){
            count++;
            cur = cur.next;}return count;}

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

图解：

代码实现：

//删除所有值为key的节点publicListNoderemoveAllKey(int key){if(null==this.head){returnnull;}ListNode prev =this.head;ListNode cur =this.head.next;while(cur !=null){if(key == cur.val){
                prev.next = cur.next;
                cur = cur.next;}else{
                prev = cur;
                cur = cur.next;}}//处理头if(key ==this.head.val){this.head =this.head.next;}returnthis.head;}

（8）清空

图解：

代码实现：

publicvoidclear(){//粗暴//this.head = null;//体面while(this.head !=null){ListNode cur =this.head.next;this.head.next =null;this.head = cur.next;}}

三、总结及思考

学习数据结构的方法：
多画图——多思考——多敲代码，一起加油吧，少年！