链表(Linked List)是一种常见的数据结构,用于存储和组织数据。它由一系列节点(Node)组成,每个节点包含两个主要部分:数据域(Data)和指针域(Pointer)。
数据域存储节点所需的数据或信息,可以是任意类型的数据,如整数、字符、对象等。指针域则指向链表中的下一个节点,将节点连接起来形成链表结构。
链表中的节点并不一定按照物理上的连续位置存储,而是通过指针域相互连接。这使得链表能够灵活地插入、删除和修改节点,而无需像数组那样进行元素的移动。
链表的优点是可以高效地插入和删除节点,而无需移动其他节点。然而,由于链表中的节点不是连续存储的,访问特定位置的节点需要从头部开始遍历,因此随机访问的效率较低。
在实际的应用场景中,链表的结构非常多样,以下是常见的链表结构:
在单向链表中,每个节点包含一个数据域,用于存储节点所需的数据,以及一个指针域,指向链表中的下一个节点。最后一个节点的指针域通常指向空值(NULL),表示链表的结束。
通过这种方式,节点之间通过指针链接在一起,形成一个链表结构。链表的头部节点通过外部引用进行访问,然后可以依次遍历访问链表中的每个节点。
由于单向链表只有一个方向的指针,所以只能从头部节点开始顺序遍历访问,无法直接访问后续节点,也无法在常量时间内进行反向遍历。
单向链表在插入和删除节点时具有较好的性能,因为只需要修改节点的指针,而不需要移动其他节点。然而,在访问特定位置的节点时,需要从头部节点开始遍历整个链表,导致访问效率较低。
以下是双向链表的结构示意图:
在双向链表中,每个节点包含一个数据域和两个指针域。除了指向下一个节点的指针域(Next Pointer),还有一个指向前一个节点的指针域(Prev Pointer)。头部节点的 Prev Pointer 通常指向空值(NULL),尾部节点的 Next Pointer 也指向空值。
通过 Prev Pointer 和 Next Pointer,双向链表允许在链表的两个方向上遍历和访问节点。这使得在某些情况下,例如在链表末尾插入或删除节点,可以更高效地操作链表。
与单向链表相比,双向链表的操作稍微复杂一些,因为每个节点需要维护两个指针。但双向链表提供了更多的功能和灵活性,如可以从头部或尾部快速插入或删除节点,以及可以在两个方向上进行遍历和搜索。
带头结点的链表在头部添加了一个额外的节点作为头结点(Header Node)或哑节点(Dummy Node),这个头结点不存储任何实际的数据。
以下是带头结点的链表的结构示意图:
头结点位于链表的起始位置,其主要作用是方便链表的操作和管理。它不存储实际的数据,只包含一个指针域,指向链表中的第一个实际节点。
带头结点的链表的优点在于简化了链表的操作。它确保链表中始终存在一个非空节点,简化了插入、删除和遍历等操作的实现。此外,头结点可以用于存储链表的一些统计信息或提供其他便利的功能。
在带头结点的链表中,链表的第一个实际节点为头结点的下一个节点。通过头结点,可以轻松地访问链表中的实际数据节点,并进行相应的操作。
当遍历带头结点的链表时,通常从头结点的下一个节点开始,直到遇到指针域为 NULL 的节点,表示链表结束。
以下是循环链表的结构示意图:
在循环链表中,每个节点仍然包含数据域和指针域,但最后一个节点的指针域不再指向空值(NULL),而是指向链表的头部节点。
这样的设计使得链表形成一个循环结构,可以通过任何节点开始遍历整个链表。从任何节点出发,通过指针的循环跳转,可以访问链表中的所有节点。
循环链表的优点在于在遍历和操作链表时,不需要考虑链表的结束位置。无论从哪个节点开始遍历,总能回到起始位置,避免了在常规链表中遇到的空指针异常。
在Java中,LinkedList(链表)是Java集合框架提供的一个实现了List接口的类。它是基于双向链表结构实现的,可以用于存储和操作元素的有序集合。
继承体系结构如下:
LinkedList类提供了以下几种构造方法:
LinkedList<String> list = new LinkedList<>();
List<String> collection = new ArrayList<>();
collection.add("Element 1");
collection.add("Element 2");
LinkedList<String> list = new LinkedList<>(collection);
LinkedList<String> originalList = new LinkedList<>();
originalList.add("Element 1");
originalList.add("Element 2");
LinkedList<String> newList = new LinkedList<>(originalList);
LinkedList类提供了许多用于操作链表的方法。以下是一些常见的操作方法:
add(E element)
:在链表末尾添加一个元素。addFirst(E element)
:在链表开头添加一个元素。addLast(E element)
:在链表末尾添加一个元素。LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.addFirst("Element 0");
list.addLast("Element 2");
get(int index)
:获取指定位置的元素。getFirst()
:获取链表的第一个元素。getLast()
:获取链表的最后一个元素。LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
String element = list.get(0);
String firstElement = list.getFirst();
String lastElement = list.getLast();
remove(int index)
:删除指定位置的元素。removeFirst()
:删除链表的第一个元素。removeLast()
:删除链表的最后一个元素。LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
list.remove(0);
list.removeFirst();
list.removeLast();
contains(Object element)
:检查链表是否包含指定元素。LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
boolean containsElement = list.contains("Element 1");
size()
:获取链表中元素的个数。isEmpty()
:检查链表是否为空。clear()
:清空链表中的所有元素。LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
int size = list.size();
boolean isEmpty = list.isEmpty();
list.clear();
在LinkedList中,可以使用不同的方式进行遍历操作。下面是几种常见的遍历方法:
LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
for (int i = 0; i < list.size(); i++) {
String element = list.get(i);
// 处理当前元素
System.out.println(element);
}
LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
for (String element : list) {
// 处理当前元素
System.out.println(element);
}
LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String element = iterator.next();
// 处理当前元素
System.out.println(element);
}
LinkedList<String> list = new LinkedList<>();
list.add("Element 1");
list.add("Element 2");
list.stream().forEach(element -> {
// 处理当前元素
System.out.println(element);
});
import java.util.Stack;
public class MyLinkList {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
private ListNode head; // 标记双向链表的头部
private ListNode tail; // 标记双向链表的尾部
// 头插
public void addFirst(int data) {
if (this.head == null) {
this.head = new ListNode(data);
this.tail = this.head;
} else {
ListNode node = new ListNode(data);
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
//尾插
public void addLast(int data) {
if (this.tail == null) {
this.tail = new ListNode(data);
this.head = this.tail;
} else {
ListNode node = new ListNode(data);
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index, int data) {
if (index < 0 || index > size()) {
System.out.println("index位置不合法!");
return false;
}
if (index == 0) {
addFirst(data);
} else if (index == size()) {
addLast(data);
} else {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
ListNode node = new ListNode(data);
ListNode prev = cur.prev;
cur.prev = node;
node.next = cur;
prev.next = node;
node.prev = prev;
}
return true;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
// 链表为空
if (head == null) {
return;
} else if (head.val == key) {
// 要删除的元素在头
head = head.next;
if (head == null)
return;
head.prev = null;
} else if (tail.val == key) {
// 要删除的元素在尾
tail = tail.prev;
tail.next = null;
} else {
// 正常情况
ListNode cur = head;
// 注意考虑只有一个元素的情况
while (cur.next != null && cur != tail) {
if (cur.val == key) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
return;
}
cur = cur.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key) {
// 空链表
if (null == head) {
return;
}
// 从头开始,出现连续的key
while (head.val == key) {
head = head.next;
if (head == null) {
return;
}
head.prev = null;
}
// 从尾开始出现连续的key
while (tail.val == key) {
tail = tail.prev;
if (tail == null)
return;
tail.next = null;
}
// 其他情况,注意只有一个元素的情况
ListNode cur = head;
while (cur.next != null && cur != tail) {
if (cur.val == key) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
cur = cur.next;
}
}
//得到单链表的长度
public int size() {
int cnt = 0;
ListNode cur = head;
while (cur != null) {
cnt++;
cur = cur.next;
}
return cnt;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
private void _display2(ListNode node) {
if (node == null) {
return;
}
if (node.next == null) {
System.out.print(node.val + " ");
return;
}
_display2(node.next);
System.out.print(node.val + " ");
}
// 递归逆序打印链表
public void display2() {
ListNode node = this.head;
_display2(node);
System.out.println();
}
public void _display3(ListNode node) {
if (node == null)
return;
Stack<ListNode> stack = new Stack<>();
while (node != null) {
stack.push(node);
node = node.next;
}
while (!stack.isEmpty()) {
System.out.print(stack.pop().val + " ");
}
System.out.println();
}
// 利用栈逆序打印链表
public void display3() {
ListNode node = this.head;
_display3(node);
}
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode curNext = cur.next;
cur.val = 0;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.head = this.tail = null;
}
}
LinkedList和ArrayList是Java集合框架中的两种不同的List实现,它们有以下几个区别:
底层数据结构:LinkedList底层基于链表实现,而ArrayList底层基于动态数组实现。
插入和删除操作:由于LinkedList是基于链表的数据结构,插入和删除元素的操作比较高效,时间复杂度为O(1),因为只需要调整节点的指针。而ArrayList的底层是动态数组,插入和删除操作需要移动其他元素,时间复杂度为O(n),其中n是元素的数量。
随机访问:ArrayList支持高效的随机访问,可以通过索引快速获取元素,时间复杂度为O(1)。而LinkedList需要从头开始遍历链表才能找到指定位置的元素,时间复杂度为O(n),其中n是索引位置。
内存消耗:由于LinkedList需要额外的指针来维护节点之间的连接关系,因此在存储相同数量的元素时,LinkedList通常会占用更多的内存空间。而ArrayList只需要连续的内存空间来存储元素。
迭代器性能:对于迭代器遍历操作,LinkedList的性能较好,因为只需要遍历链表中的节点即可。而ArrayList在使用迭代器遍历时,由于底层是数组,可能会导致性能稍差。
总而言之,当需要频繁进行插入和删除操作,而对于随机访问的需求较少时,LinkedList可能是更好的选择。而当需要频繁进行随机访问,而插入和删除操作较少时,ArrayList更为适合。
文章浏览阅读476次。FhqTreap&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;amp;ThinSpace;\ \ \ \ \ \ \ \,&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&a_qfrtpa
文章浏览阅读7.7k次,点赞3次,收藏33次。这里是引用上机一样式body{ border:0px; padding:0px; margin:0px auto; font:12px Tahoma;}div,ul,li,dt,dl { float:left; margin:0px auto; padding:0px;}li{ list-style:none;}a:..._使用jquery快速高效制作网页交互特效上机操作
文章浏览阅读646次。实验环境:VMware虚拟机1台,配置如下:vCPU >=1CMEM >=1GDISK >=20GOS=Linux CentOS7.x网络适配器=NAT配置IP、DNS等,使虚拟机可以连通互联网使用xshell或者secureCRT工具连接实验准备:#cd /etc/yum.repos.d 进入yum配置目录#mkdir backup 创建备份目录#m..._docker 兼用云盘与博客
文章浏览阅读1k次。vnc远程工具不知道大家听说过没有,它的中文名叫虚拟网络控制台,这是一款优秀的远程控制工具软件。相信大家看到远程控制软件应该已经猜出来了这款软件到底是干嘛的了吧。大家找到过很好用过的vnc远程工具吗?今天来给大家介绍一款非常好用的vnc远程工具吧。教你怎么进行vnc远程工具的下载和安装。使用工具:IIS7服务器管理工具这款软件的vnc功能其实已经是很齐全的了,操作使用非常的方便。它不仅可以批量打开链接,也可以群控操作,操作一台等于同时操作N台。这可以说是非常方便好用了。强烈推荐一下。IIS7服务器管理_亲这是远程工具下载安装一下,设备代码和密码发我,远程工具不要关闭给您远程。:htt
文章浏览阅读284次。从程序员的角度看linux和windows的对比:一 系统架构的对比1 内核(1) 内核的弹性内核内核的弹性linux的内核表现出了高度的可配置性和独立性,主要是完成:io驱动设备管理,tcp/ip,以及任务调度.linux的标准内核发布版本有40~50mb,而我现在在一些评估板上试验的嵌入式linux系统(使用arm或m68k系列的cpu)只用到了2mb,同样实现了网络功能和完整的任务调度,这使..._linux和vs的区别
文章浏览阅读5k次,点赞12次,收藏34次。详细记录用法,清晰明了!np.expand_dims(a, axis = 0 )np.expand_dims(a, axis = 1 )np.expand_dims(a, axis = 2 )np.expand_dims(a, axis = 3 )np.expand_dims(a, axis = -1 )_np.expand
文章浏览阅读63次。1.我们需要理解报社、订阅系统和订报人之间的关系,订报人通过订阅系统订报,一旦报社有新的报纸,订阅系统就会派人送或者邮寄给订报人新的报纸。然后,出版者+订阅者就是观察者模式,只不过名称不一样,主题(Subject,或者叫做Observabler)类比于出版者,是事件发生的主体,订阅者改称为观察者(Observer),是响应事情发生的主体。该模式定义了对象之间的一对多依赖,这样一来,当一个对..._修改 `weatherdata` 注册、注销、通知观察者的方法:
文章浏览阅读2.5k次。ProgressBar_对话框与标题栏进度条:package com.example.progressbar;import android.app.Activity;import android.app.ProgressDialog;import android.os.Bundle;import android.view.Menu;import android.view.MenuItem;_android progress 进度条
文章浏览阅读397次。正常的话我们启用的chrome浏览器是不带插件的,如果你能登陆chrome的话,你会发现登陆信息也没有,还有不管你怎样设置每次新打开的chrome都是默认设置的。我们正常启动的浏览器每次都要加载配置文件的,一般的配置文件就是在user data里,插件就是属于配置文件的一部分。 我们做的工作就是让我们每次启动时都调用一下配置文件就好了。正常我们调用浏览器一行代码就好了。driver = ..._chromedriver 启用自带插件
文章浏览阅读4.6k次,点赞8次,收藏54次。对于程序员来说,使用MarkDown编辑器远远比使用word等编辑器好,统一自然、代码高亮等特点已经成为了程序员的必备编辑器。那么如何使自己开发的页面也具备markdown编辑器的功能呢?下载与安装1.下载开源的编辑器插件 Markdown.zip方法一:官网下载:https://pandao.github.io/editor.md/ —速度有点慢,有点难下载方法二:百度网盘 https://pan.baidu.com/s/1JzoQR17zopU9t7Jq7XWvvg 提取码:qdlz —推_dw如何添加类似markdown的编辑器
文章浏览阅读2.5k次,点赞3次,收藏13次。3-7-6银行业务队列简单模拟设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时,B窗口处理完1个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。输入格式:输入为一行正整数,其中第1个数字N(≤1000)为顾..._设某银行有a、b两个业务窗口,且处理业务的速度不一样,其中a窗口处理速度是b窗口的
文章浏览阅读78次。 故事的发生起于,由于老板强烈要求app在iPhone6和5有一样的工具栏,然后前端妹子用@media为iPhone6和Plus做了样式适配。然后问题来了,竟然奇葩的发现@media样式只对iPhone4和5起了作用,然后在6和6S的样式效果和5是一样的,奇了怪了! 然后我去查找原因,无意中去获取设备屏幕宽高时发现了这神奇的现象:CGRect screenBounds = [[UI..._ios的闪屏适配