共计 7832 个字符,预计需要花费 20 分钟才能阅读完成。
今日目录:
1:可能说出链表的存储构造和特点
2:可能说出链表的几种分类及各自的存储构造
3:能说出链表和数组的差别
4:实现实战演练题目
5:实现综合案例
1、概念及存储构造
问题:思考一下动静数组 ArrayList 存在哪些弊病?
1:插入,删除工夫复杂度高
2:可能会造成内存空间的大量节约
3:须要一块间断的存储空间,对内存的要求比拟高,比方咱们要申请一个 1000M 的数组,如果内存中没有间断的足够大的存储空间则会申请失败,即使内存的残余可用空间大于 1000M,依然会申请失败。
论断:是否做到用多少内存空间就申请多少内存?
链表(Linked list)是一种物理 存储单元上非间断、非程序 的存储构造,链表中的每一个元素称之为 结点(Node),结点之间用指针(援用)连接起来,指针的指向程序代表了结点的逻辑程序,结点能够在运行时动静生成。每个结点包含两个局部:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
链表能解决数组不能解决的事件吗?
1:链表天生就具备动静扩容的特点,不须要像动静数组那样先申请一个更大的空间,而后将原空间内的数据拷贝到新空间;可能防止内存空的大量节约
2:链表不须要一块间断的内存空间,它通过指针将一组 零散的内存块 串联起来应用,所以如果咱们申请一个 1000M 大小的链表,只有内存残余的可用空间大于 1000M,便不会呈现问题。
然而需注意:存储同样的数据,链表要比数组消耗内存!
2、链表分类
链表依据其结点之间的连贯模式咱们又可分为:单链表,双向链表,循环链表,双向循环链表
2.1、单链表
单链表就是咱们刚刚讲到的链表的最根本的构造,链表通过 指针 将一组零散的内存块串联在一起。。如图所示,咱们把这个记录下个结点地址的指针叫作 后继指针 next,如果链表中的某个节点为 p,p 的下一个节点为 q,咱们能够示意为:p.next=q
链表中有两个结点是比拟非凡的,它们别离是第一个结点和最初一个结点。咱们习惯性地把第一个结点叫作头结点,把最初一个结点叫作尾结点。其中,头结点用来记录链表的基地址, 有了它,咱们就能够遍历失去整条链表。而尾结点非凡的中央是:指针不是指向下一个结点,而是指向一个空地址 NULL,示意这是链表上最初一个结点。
与数组一样,链表也反对 数据的查找、插入和删除操作。
在进行数组的插入、删除操作时,为了放弃内存数据的连续性,须要做大量的数据搬移,所以工夫复杂度是 O(n)。而在链表中插入或者删除一个数据,咱们并不需要为了放弃内存的连续性而搬移结点,因为链表的存储空间自身就不是间断的。所以,在链表中插入和删除一个数据是十分疾速的。
如图所示,针对链表的插入和删除操作,咱们只须要思考相邻结点的指针扭转,所以 插入删除的工夫复杂度是 O(1)。
然而,无利就有弊。链表要想随机拜访第 k 个元素,就没有数组那么高效了。因为链表中的数据并非间断存储的,所以无奈像数组那样,依据首地址和下标,通过寻址公式就能间接计算出对应的内存地址,而是须要依据针一个结点一个结点地顺次遍历,直到找到相应的结点,所以,链表随机拜访的性能没有数组好,查问的工夫复杂度是 O(n)。
2.2、双向链表
单向链表只有一个方向,结点只有一个后继指针 next。而双向链表,顾名思义,它反对两个方向,每个结点不止有一个后继指针 next 指向前面的结点,还有一个前驱指针 prev 指向后面的结点,如图所示
从图中能够看进去,双向链表须要额定的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。尽管两个指针比拟节约存储空间,但能够反对双向遍历,这样也带来了双向链表操作的灵活性,比方
1:能够在 O(1)工夫内找到给定结点的前驱节点,而对于单链表则须要 O(n)的工夫
2:依据索引来查找元素时可极大晋升查找效率
…..
在很多场景下双向链表都比单向链表更加高效,这就是为什么在理论的软件开发中,双向链表只管比拟费内存,但还是比单链表的利用更加宽泛的起因。如果你相熟 Java 语言,你必定用过 LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理,就会发现其中就用到了双向链表这种数据结构。
实际上,这里有一个更加重要思维就是 用空间换工夫的设计思维。当内存空间短缺的时候,如果咱们更加谋求代码的执行速度,咱们就能够抉择空间复杂度绝对较高、但工夫复杂度绝对很低的算法或者数据结构。相同,如果内存比拟紧缺,比方代码跑在手机等存储容量小的设施上,这个时候,就要反过来用工夫换空间的设计思路。比方最典型的缓存零碎就是一个用空间换工夫的思维。
2.3、循环链表
循环链表是一种非凡的单链表。实际上,循环链表也很简略。它跟单链表惟一的区别就在尾结点。咱们晓得,单链表的尾结点指针指向空地址,示意这就是最初的结点了。而 循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中,你应该能够看进去,它像一个环一样首尾相连,所以叫作“循环”链表,和单链表相比,循环链表的长处是从链尾到链头比拟不便。当要解决的数据具备环型构造特点时,就特地适宜采纳循环链表,循环链表的构造如图所示
2.4、双向循环链表
理解了循环链表和双向链表,如果把这两种链表整合在一起就是一个 双向循环链表
3、小结 & 实战
3.1、链表数组比照
数组和链表是两种截然不同的内存组织形式。正是因为内存存储的区别,它们插入、删除、随机拜访操作的工夫复杂度正好相同,下图表明了链表和数组在插入删除和随机拜访上工夫复杂度的比照
3.2、206. 反转链表
字节跳动,腾讯,阿里,美团点评最近面试题,206. 反转链表
高频题
双指针迭代
class Solution {public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr !=null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
3.3、141. 环形链表
阿里,腾讯,百度最近面试题,141. 环形链表
快慢指针
public class Solution {public boolean hasCycle(ListNode head) {
// 非凡判断
if (head == null || head.next == null) {return false;}
ListNode fast = head;
ListNode slow = head;
// 两个指针别离下后走
while (true) {
fast = fast.next.next;
slow = slow.next;
if (fast == null || fast.next == null) {return false;}
if (fast == slow) {break;}
}
return true;
}
}
4、综合案例
4.1、需要
在学习数组的时候咱们基于数组实现了一个 List 容器,反对数据的增加,批改,删除,查问等操作,明天学习完链表之后可能基于链表来实现一个 LinkedList 容器呢?
要求:
1:要求和动静数组 ArrayList 具备雷同的性能
2:请基于双向链表实现,
4.2、实现
(1)定义接口,com.itheima.linkedlist.inf.List
,接口办法跟之前实现 ArrayList 时一样,只不过增加上泛型
package com.itheima.linkedlist.inf;
/**
* Created by 传智播客 * 黑马程序员.
*/
public interface List<E> {
/**
* 返回容器中元素的个数
* @return
*/
int size();
/**
* 判断容器是否为空
* @return
*/
boolean isEmpty();
/**
* 查问元素在容器中的索引下标
* @param o 元素对象
* @return 在容器中的下标 不存在则返回 -1
*/
int indexOf(E o);
/**
* 判断容器是否蕴含某个特定的元素
* @param e
* @return
*/
boolean contains(E e);
/**
* 将元素增加到容器结尾
* @param e 要增加的元素
* @return 是否增加胜利
*/
boolean add(E e);
/**
* 向指定地位增加元素
* @param index 地位下标
* @param element 元素对象
*/
void add(int index, E element);
/**
* 用指定的元素替换指定地位的数据
* @param index 指定的地位索引下标
* @param element 新的元素
* @return 原始的元素
*/
E set(int index, E element);
/**
* 获取指定地位的元素
* @param index 索引下标
* @return 该地位的元素
*/
E get(int index);
/**
* 移除指定地位的元素
* @param index 索引下标
* @return 被移除的元素
*/
E remove(int index);
/**
* 革除容器中所有元素
*/
void clear();}
(2)创立接口实现:com.itheima.linkedlist.LinkedList
,实现对应接口
(3)容器要基于双向链表实现,链表是由一个一个结点形成的,因而定义链表结点对象,编写一个动态的外部类
// 定义链表结点对象
private static class Node<E>{
E val;
Node<E> prev;
Node<E> next;
// 定义结构
public Node(Node<E> prev,E val,Node<E> next){
this.prev = prev;
this.val = val;
this.next = next;
}
}
(4)定义相干的成员变量
// 定义容器中元素的个数
int size;
// 定义链表的头结点
Node<E> first;
// 定义链表的尾结点
Node<E> last;
(5)实现 size,isEmpty,indexOf,contains
等办法的编写
@Override
public int size() {return size;}
@Override
public boolean isEmpty() {return size == 0;}
@Override
public int indexOf(E o) {
int index = 0;
// 分状况 o 是否为 null,为 null 和不为 null 判断的形式不一样,null 是用 ==,不为 null 用 equals
if (o == null) {for ( Node x = first;x!=null;x=x.next) {if (x.val == null) {return index;}
index++;
}
}else {for ( Node x = first;x!=null;x=x.next) {if (o.equals(x.val)) {return index;}
index++;
}
}
return -1;
}
@Override
public boolean contains(E e) {return indexOf(e) != -1;
}
(6)实现 add
办法的编写
@Override
public boolean add(E e) {
// 增加是将元素值增加到链表尾部
linkLast(e);
return true;
}
private void linkLast(E e) {
Node l = last;
Node newNode = new Node(l,e,null);
last = newNode;
if (l==null) {
// 第一次增加
first = newNode;
}else {l.next = newNode;}
size++;
}
@Override
public void add(int index, E element) {
// 查看索引
checkIndex(index);
if (index == size) {linkLast(element);
}else {linkBefore(element,node(index));
}
}
/**
* 在指定结点前增加一个元素
* @param element
* @param node
*/
private void linkBefore(E element, Node<E> node) {
Node<E> prev = node.prev;
Node<E> newNode = new Node<E>(prev,element,node);
node.prev = newNode;
if (prev == null) {first = newNode;}else {prev.next = newNode;}
size++;
}
/**
* 查找索引为 index 的结点
* @param index
* @return
*/
private Node<E> node(int index){
// 折半查找
if (index < (size >> 1)) {
// 从头开始查找
Node<E> f = first;
for (int i = 0;i< index;i++) { //i<index 留神不能是 i <=index 因为当 i =index- 1 时 f=f.next 其实 f 曾经指向了索引为 index 地位的元素了
f = f.next;
}
return f;
}else {
// 从尾开始查找
Node<E> l = last;
for (int i=size-1;i> index;i--) {// 同上
l = l.prev;
}
return l;
}
}
private void checkIndex(int index) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("index"+index+",size="+size);
}
}
(7)实现 set,get
办法的编写
/**
* 替换指定索引地位的元素
* @param index 指定的地位索引下标
* @param element 新的元素
* @return
*/
@Override
public E set(int index, E element) {isElementIndex(index);
Node<E> oldNode = node(index);
E oldVal = oldNode.val;
oldNode.val = element;
return oldVal;
}
private void isElementIndex(int index) {if (index < 0 || index >=size) {throw new IndexOutOfBoundsException("index="+index+",size="+size);
}
}
@Override
public E get(int index) {isElementIndex(index);
return node(index).val;
}
(8)实现 remove
办法的编写
@Override
public E remove(int index) {isElementIndex(index);
Node<E> node = node(index);
return unlink(node);
}
private E unlink(Node<E> node) {
Node<E> prev = node.prev;
Node<E> next = node.next;
E val = node.val;
node.val = null;
//node 是头结点
if (prev == null) {first = next;}else {
prev.next = next;
node.prev = null;
}
//node 是尾结点
if (next == null) {last = prev;}else {
next.prev = prev;
node.next = null;
}
size--;
return val;
}
(9)实现 clear,toString
办法的编写
@Override
public void clear() {for (Node l = first;l!=null;) {
Node next = l.next;
l.val = null;
l.prev = null;
l.next = null;
l = next;
}
first = last = null;
size=0;
}
@Override
public String toString() {
// 输入 1->2->Null 格局的数据
StringBuilder stringBuilder = new StringBuilder();
for (Node l=first;l!=null;l = l.next) {stringBuilder.append(l.val).append("->");
}
stringBuilder.append("Null");
return stringBuilder.toString();}
(10)编写测试类:com.itheima.linkedlist.LinkedListTest
public static void main(String[] args) {List list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
System.out.println("容器内元素为:"+list); // 1->2->3->Null
System.out.println("容器内元素个数:"+list.size()+"容器是否为空:"+list.isEmpty());
System.out.println("容器中是否蕴含 3:"+list.contains(3));
list.add(0,4);// 4->1->2->3->Null
System.out.println("容器内元素为:"+list);
list.add(3,5);//4->1->2->5->3->Null
System.out.println("容器内元素为:"+list);
list.add(2,6);//4->1->6->2->5->3->Null
System.out.println("容器内元素为:"+list);
System.out.println("获取索引为 0 的元素:"+list.get(0));
System.out.println("获取索引为 5 的元素:"+list.get(5));
System.out.println("获取索引为 2 的元素:"+list.get(2));
list.remove(0);//1->6->2->5->3->Null
System.out.println("容器内元素为:"+list);
list.remove(3);//1->6->2->3->Null
System.out.println("移除后容器内元素为:"+list);
list.clear();
System.out.println("清空后为:"+list);
}
查看输入后果!
容器内元素为:1->2->3->Null
容器内元素个数:3 容器是否为空:false
容器中是否蕴含 3:true
容器内元素为:4->1->2->3->Null
容器内元素为:4->1->2->5->3->Null
容器内元素为:4->1->6->2->5->3->Null
获取索引为 0 的元素:4
获取索引为 5 的元素:3
获取索引为 2 的元素:6
容器内元素为:1->6->2->5->3->Null
移除后容器内元素为:1->6->2->3->Null
清空后为:Null
本文由传智教育博学谷 – 狂野架构师教研团队公布,转载请注明出处!
如果本文对您有帮忙,欢送关注和点赞;如果您有任何倡议也可留言评论或私信,您的反对是我保持创作的能源