注册

算法与数据结构之链表

个人说明:拿过国内某算法大赛全国三等。。。(渣渣)


概念

链表是计算机数据结构中比较重要的一个,也是最基础之一。在开发过程中,有些时候会采用这种结构。链表可以说是一种动态的数据结构。
链表是一种物理存储上非连续的存储结构,数据的顺序与关联通过链表中的节点指针来实现。结点可以动态变更,那也就说明链表这种结构可快速添加数据。
链表是一种线性表结构

链表分类(以下图都是盗的,有侵的话私聊我)

单链表

链表中的元素的指向只能指向链表中的下一个元素或者为空,元素之间不能相互指向,是一种线性链表
在这里插入图片描述

循环链表

在单向链表和双向链表的基础上,将两种链表的最后一个结点指向第一个结点从而实现循环
在这里插入图片描述

双向链表

每个节点既有指向下一个元素的指针,又有指向前一个元素的指针,其中每个结点都有两种指针
在这里插入图片描述

基本单位

节点
包含下一节点(上一节点)指针与数据

基本操作

就拿单链表作为示例(其他链表操作没太大区别)


删除节点

在这里插入图片描述
删除头节点:
直接让root节点指向头节点的下一个节点
删除中间节点:
直接让中间节点的前一个节点指向当前节点的下一个节点
删除尾节点:
直接让当前尾节点的上一个节点指向null

添加节点

在这里插入图片描述
增加的新节点会指向当前节点的下一个,那么当前节点的下一个又会指向新的节点。很快就增加了一个新节点。
添加节点如果在头部的话,root指到新节点,新节点的下一个节点指向旧root
添加尾节点的话,就让尾节点的下一个节点指向新节点
例:java的LinkedList(本文针对的是1.7的源码)
首先,先看看LinkedList的初始化,源码如下:
LinkedList包含3个全局参数,
size存放当前链表有多少个节点。
first为指向链表的第一个节点的引用。
last为指向链表的最后一个节点的引用。

// 什么都没做,是一个空实现
public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
// 检查传入的索引值是否在合理范围内
checkPositionIndex(index);
// 将给定的Collection对象转为Object数组
Object[] a = c.toArray();
int numNew = a.length;
// 数组为空的话,直接返回false
if (numNew == 0)
return false;
// 数组不为空
Node<E> pred, succ;
if (index == size) {
// 构造方法调用的时候,index = size = 0,进入这个条件。
succ = null;
pred = last;
} else {
// 链表非空时调用,node方法返回给定索引位置的节点对象
succ = node(index);
pred = succ.prev;
}
// 遍历数组,将数组的对象插入到节点中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}

if (succ == null) {
last = pred; // 将当前链表最后一个节点赋值给last
} else {
// 链表非空时,将断开的部分连接上
pred.next = succ;
succ.prev = pred;
}
// 记录当前节点个数
size += numNew;
modCount++;
return true;
}

Node节点类:


    private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;

Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

addFirst/addLast


public void addFirst(E e) {
linkFirst(e);
}

private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f); // 创建新的节点,新节点的后继指向原来的头节点,即将原头节点向后移一位,新节点代替头结点的位置。
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}

getFirst/getLast


public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

get方法,在操作时候会判断索引位置,来从后或从前找,提升查找效率


public E get(int index) {
// 校验给定的索引值是否在合理范围内
checkElementIndex(index);
return node(index).item;
}

Node<E> node(int index) {
//如果索引小于size的一半则从前往后找,如果大于则从后往前找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

removeFirst/removeLast


public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
//摘掉头结点,将原来的第二个节点变为头结点,改变frist的指向
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}

有关链表的算法

以下算法只给思路(代码写一写就知道了)


链表算法注意事项

并没什么可注意的,哈哈哈哈
在这里插入图片描述
有一点就是:链表的插入和删除操作O(1)的复杂度(主要就是结构可以让他这么屌)

算法一(单链表的倒数第K个结点)

这是个比较简单的算法
思路:由于单链表的结构无法从链表尾节点来倒序查找,那么你可以两个节点相差k-1来计算倒数k个节点,如果节点1的next是空,那么节点2就是你要找的。

算法二(判断一个链表有环)

首先创建两个指针1和2,同时指向这个链表的头节点。让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。


算法三(两个链表的第一个公共结点)

将两个链表的节点分别存在两个栈中,


生活中的算法(排排坐,赶走第三者)

题目:
有100人排排坐,从第一个人开始,喊号(1,2,3)。第一个人喊1,第二个人喊2,第三个人喊3,这时候第三个人就出队,第四个人开始喊1,如此循环,最后剩下哪个人?
思路:
循环链表,把100个人放到循环链表里,循环每次到三时候,把三这个删除节点,继续循环,直到一个节点的next指针指到自己,结束循环。

1 个评论

讲链表把适配链表的算法也搭配上,不错点赞

要回复文章请先登录注册