前言
什么是链表
含义：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
图形解释：
逻辑上是连续的，但物理上看起来不连续
这个图形也叫单向不带头非循环
链表的结构
非常多样，有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） @Override public void addFirst(int data) { //先实例化一个节点 ListNode node = new ListNode(data); //如果链表没有节点，那么插入的这个节点就是第一个节点 //所以head = node if (this.head ==null){ this.head = node; }else { node.next = this.head; this.head = node; } }
尾插法
//尾插法:在最后创建一个节点 //时间复杂度O（N） @Override public 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; } //任意位置插一个节点 @Override public 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; }
链表中是否包含某个数字
//链表是否包含某个数字 @Override public boolean contains(int key) { ListNode cur = this.head; while(cur != null){ if (cur.val == key){ return true; } cur = cur.next; } return false; } @Override public 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; } @Override public 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 @Override public 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的区别
总结
以上就是关于链表的详细知识。
