【链表的说明、方法---顺序表与链表的区别】

---

前言

什么是链表

含义：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

图形解释：
逻辑上是连续的，但物理上看起来不连续
这个图形也叫单向不带头非循环

链表的结构

非常多样，有8种结构

重点掌握下面两种：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

带头和不带头的区别

链表的实现（方法）

定义接口

public interface ILIst {// 1、无头单向非循环链表实现//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}

遍历链表

1.怎么从一个节点走到下一个节点
head = head.next

2.怎么判断所有节点遍历完了
当head = null 循环结束

//            while(head != null){
//                System.out.print(head.val+" ");
//                head = head.next;
//            }//这个方法遍历完head=null,会导致链表空了，找不到第一个节点在哪了
//所以应该把head赋值给一个数，让它去遍历，相当于head的分身，分身消失了，主体head还在ListNode cur = this.head;//进入循环条件为链表不为空//也就是说当head为空时，循环结束while(cur != null){System.out.print(cur.val+" ");cur =cur.next;}

头插法

    //头插法//时间复杂度O（1）@Overridepublic void addFirst(int data) {//先实例化一个节点ListNode node = new ListNode(data);//如果链表没有节点，那么插入的这个节点就是第一个节点//所以head = nodeif (this.head ==null){this.head = node;}else {node.next = this.head;this.head = node;}}

尾插法

    //尾插法:在最后创建一个节点//时间复杂度O（N）@Overridepublic void addLast(int data) {//创建一个新节点ListNode node = new ListNode(data);ListNode cur = this.head;//当链表为空时，此案件的新节点就是第一个节点if (this.head == null){this.head = node;}else {//让cur遍历完走到cur.next为空时，才找到了最后一个节点//意思就是走出了while循环，就说明cur走到了最后一个节点上while (cur.next != null){cur = cur.next;}cur.next = node;node.next =null;}}

任意位置插入一个节点

    //让cur去到index-1位置private ListNode searchPrev(int index){ListNode cur = this.head;int count =0;while(count != index-1){cur = cur.next;count++;}//循环走完, cur已经走到index-1得位置了return cur;}//任意位置插一个节点@Overridepublic void addIndex(int index, int data) {ListNode node = new ListNode(data);//检查index得合法性if (index < 0 || index > size()){//抛自定义异常return ;}//如果index=0 头插法if (index == 0){addFirst(data);return;}//如果index=size,尾插法if (index == size()){addLast(data);return;}ListNode cur =  searchPrev(index);//调用cur走到index-1的方法node.next = cur.next;cur.next = node;}

链表中是否包含某个数字

    //链表是否包含某个数字@Overridepublic boolean contains(int key) {ListNode cur = this.head;while(cur != null){if (cur.val == key){return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {}

删除链表某个节点

    //让cur走到要删除的节点的前一个节点private ListNode findPrev(int key){ListNode cur = this.head;//判断条件是cur不能超过倒数二个节点while(cur.next != null ){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}@Overridepublic void remove(int key) {//如果链表为空,无法删除if (this.head == null){return ;}//如果要删除第一个节点if (this.head.val ==key){this.head = this.head.next;return;}//判断前驱ListNode cur = findPrev(key);//判断返回值是否为空if (cur == null){System.out.println("没有你要删除的数字！");return ;}//删除ListNode del = cur.next;cur.next = del.next;}

删除链表中所有关键字key

    //删除链表中所有关键字key@Overridepublic void removeAllKey(int key) {if (this.head == null){return;}ListNode prev = this.head;ListNode cur = this.head.next;while(cur != null){if (cur.val == key){prev.next = cur.next;cur = cur.next;}else{prev = cur;cur = cur.next;}}if (this.head.val == key){this.head = head.next;}}

清空链表所有节点

    public void clear() {ListNode cur = this.head;while(cur != null){ListNode curNext  = cur.next;cur.next =null;cur = curNext;}this.head = null;}

ArrayList 和 LinkedList的区别

总结

以上就是关于链表的详细知识。