链表看这篇就够了

链表
1.前言2.定义3.模板设计4.单链表4.1概念4.2基本操作4.2.1添加4.2.2删除4.2.3修改4.2.4查询

5.双向链表5.1概念5.2基本操作5.2.1添加5.2.2删除5.2.3修改5.2.4查询

6.单向循环链表6.1概念6.2基本操作6.2.1添加6.2.2删除6.2.3修改6.2.4查询

7.双向循环链表7.1概念7.2基本操作7.2.1添加7.2.2删除7.2.3修改7.2.4查询

1.前言

前面我们已经学习了数组,数组容量一经定义难以改变,同时删除和插入元素需要移动大量的数据元素,效率较低。为此,引入了线性表中的链式存储结构。链式存储的数据元素不再具有连续的地址,同时可以根据需要随时申请和释放空间,更加灵活高效,但是丧失了随机访问的能⼒。

2.定义

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,是一种递归的数据结构,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

链表看这篇就够了

3.模板设计

链表看这篇就够了
设计一个List接口,里面写一些通用的操作,供其他类实现,创建抽象类AbstractList,继承List接口,实现一些通用的操作,比如判断索引是否越界之类的常用操作。

List接口

public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();

/**
* 元素的数量
* @return
*/
int size();

/**
* 是否为空
* @return
*/
boolean isEmpty();

/**
* 是否包含某个元素
* @param element
* @return
*/
boolean contains(E element);

/**
* 添加元素到尾部
* @param element
*/
void add(E element);

/**
* 获取index位置的元素
* @param index
* @return
*/
E get(int index);

/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
E set(int index, E element);

/**
* 在index位置插入一个元素
* @param index
* @param element
*/
void add(int index, E element);

/**
* 删除index位置的元素
* @param index
* @return
*/
E remove(int index);

/**
* 查看元素的索引
* @param element
* @return
*/
int indexOf(E element);
}

抽象类AbstractList

public abstract class AbstractList<E> implements List<E>  {
/**
* 元素的数量
*/
protected int size;
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}

/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}

/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}

/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}

protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}

protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}


4.单链表
4.1概念

顾名思义,单链表就是表示数据结点只有一个指针域。同时在单链表具体功能的实现中,为了让代码更加精简,统一所有节点的处理逻辑,可以在最前面增加一个虚拟的头结点的辅助结点(不存储数据)。同时,由于单链表的表头元素中没有前驱,所以创建一个指向表头结点的指针,来存储表头结点的地址,称为单链表的头指针变量,即下图中的first。

链表看这篇就够了

4.2基本操作

为了更好的实现下面的增删改查操作,我们首先首先用一个静态内部类来定义结点的抽象数据类型

	private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}

一个 Node 对象含有两个实例变量,类型分别为 E(参数类型) 和 Node。其中next用来指向下一个链表,element用来存储一个结点的数据。我们会在需要使用 Node 类的类中定义它并将它标记为 private,因为它不是为用例准备的。
然后创建一个first指针,指向头结点。

private Node<E> first;

我们再写一个node方法,用来获取index位置对应的节点对象。首先检查index值是否合理,如果合理,创建结点node指向头结点。进行index次循环,每次让结点node指向下一个结点。循环结束返回node。

/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);

Node<E> node = first.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}

同时重写indexOf方法,用来获取元素的位置,具体操作与上面类似

	@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;

node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;

node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}

4.2.1添加

链表看这篇就够了
如果要在index=0位置处插入元素,只需要让虚拟头结点的next指向新插入的结点,新插入结点的next指向原先0位置的结点。
链表看这篇就够了
如果在其他合理位置插入,只需要找到前一个结点,让他的next指向新插入的结点,新插入结点的next指向原先位置的结点。

	@Override
public void add(int index, E element) {
rangeCheckForAdd(index);

Node<E> prev = index == 0 ? first : node(index - 1);
prev.next = new Node<>(element, prev.next);

size++;
}

4.2.2删除

链表看这篇就够了
如果删除index=0位置处的结点,只需要让虚拟头结点的next指向index=1处的结点。在Java中,0位置指向1位置的next不用设置为null,曾经的结点对象没有其他结点指向它,变成了"孤儿",Java 的内存管理系统最终将回收它所占用的内存。
链表看这篇就够了
如果删除其他位置的结点,只需要找到待删除元素的前一个结点,让它指向待删除元素的下一个结点。

	@Override
public E remove(int index) {
rangeCheck(index);

Node<E> prev = index == 0 ? first : node(index - 1);
Node<E> node = prev.next;
prev.next = node.next;

size--;
return node.element;
}

4.2.3修改

	@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}

4.2.4查询

@Override
public E get(int index) {
return node(index).element;
}

5.双向链表
5.1概念

链表看这篇就够了
看图就知道,双向链表与单链表的不同之处在于每个结点都增加了一个指向其前驱的指针域,其余不变。同时呢,为了更好的操作,我们再添加一个first指针指向第一个结点,一个last指针指向最后一个结点。

当只有一个元素时
链表看这篇就够了

5.2基本操作

与单链表的操作类似,创建一个内部类Node

private static class Node<E> {
E element;
//前一结点地址
Node<E> prev;
//后一结点地址
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}

然后创建first和last指针分别指向第一个结点和最后一个结点。

private Node<E> first;
private Node<E> last;

5.2.1添加

链表看这篇就够了
如果原先链表不为空,我们在链表最后添加元素。

    我们先拿到原先的last,就命名为oldLast让新添加的node前驱结点指向oldLast,后驱结点指向null,然后让last指向新添加的结点,让oldLast的next指向新添加的结点。

当链表为空时,添加第一个元素,即oldLast为null,只需要first=last
链表看这篇就够了
同样链表有其他结点,我们在非首尾位置添加结点。

    通过node(index)获取到原先位置的结点,命名为next,通过next.prev获取原先node位置的前驱元素prev,让新添加的node元素的前驱结点指向prev,后驱结点指向next,通过next.prev = node指向新添加的元素,最后通过prev.next = node让前驱元素指向新添加的元素node。

当添加在0位置的元素时,前面获取的prev元素为null,只需要让first指向新添加的node

@Override
public void add(int index, E element) {
rangeCheckForAdd(index);

if (index == size) { // 往最后面添加元素,可能没有元素
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) { // 这是链表添加的第一个元素
first = last;
} else {
oldLast.next = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;

if (prev == null) { // index == 0
first = node;
} else {
prev.next = node;
}
}

size++;
}

5.2.2删除

链表看这篇就够了
当链表结构如上图时,删除最后一个元素

    通过node(3)获取要删除的元素node,然后分别获取到它的前驱结点prev和后继结点next。通过prev.next = next使前驱结点指向null最后让last指向prev

链表看这篇就够了
当删除第一个元素时

    通过node(0)获取要删除的元素node,然后分别获取到它的前驱结点prev和后继结点next。发现prev=null,则直接first=next,指向待删元素的下一个结点最后next.prev = prev,其实这里的prev==null

链表看这篇就够了
当删除非首尾结点时

    通过node(index)获取要删除的元素node,然后分别获取到它的前驱结点prev和后继结点next。通过prev.next = next使前驱结点指向被删元素的后一个结点最后next.prev = prev,使被删元素的后一个结点next指向被删元素的前一个结点perv
@Override
public E remove(int index) {
rangeCheck(index);

Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;

if (prev == null) { // index == 0
first = next;
} else {
prev.next = next;
}

if (next == null) { // index == size - 1
last = prev;
} else {
next.prev = prev;
}

size--;
return node.element;
}

5.2.3修改

@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}

5.2.4查询

	@Override
public E get(int index) {
return node(index).element;
}

6.单向循环链表
6.1概念

为了某些操作实现方便,常将单链表中的最后一个结点的指针域指向头结点,这样就形成了首尾相连的结构,称为循环单链表。

链表看这篇就够了
当只有一个结点时,结点的next指向自己,如下图
链表看这篇就够了

6.2基本操作

先创建一个内部类Node

private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}

然后创建first指向第一个结点。

private Node<E> first;

6.2.1添加

链表看这篇就够了
当添加元素的位置为0时

    我们先让待插入结点newFirstnext指向原先0号位置的结点如果此时的链表不为空,即size!=0,通过node(index-1)获取最后一个结点。如果此时链表为空,最后一个结点就是它自己,让它的next指向它自己。然后让最后一个结点的next指向newFirst此时的first还指向原先的第一个结点,最后将它的指针引向newFirst,即first = newFirst

链表看这篇就够了
当添加的元素位置不为0时

    首先获取待添加位置的前一个元素,比如添加新结点到三号位置,先通过node(index-1)获取前一个元素prev让prev的next指向新插入的结点,让新插入结点的next指向原先位置的元素
    @Override
public void add(int index, E element) {
rangeCheckForAdd(index);

if (index == 0) {
Node<E> newFirst = new Node<>(element, first);
// 拿到最后一个节点
Node<E> last = (size == 0) ? newFirst : node(size - 1);
last.next = newFirst;
first = newFirst;
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}

6.2.2删除

链表看这篇就够了
当删除元素为第一个时

    首先判断这个链表是不是只含这一个元素,如果只含这一个,只需要first=null,没有指针引向它,它就会被回收,也就达到了删除的目的。如果还有其它的元素,首先将first指向原先一号位置的元素,即first = first.next,然后通过node(size - 1)获取最后一个元素,使其指向原先的一号位置元素,即last.next = first
    链表看这篇就够了

当删除元素不是第一个时
1.通过node(index - 1)获取待删除元素的前一个结点prev,只需要让前一个结点的next指向待删除元素的的next,即prev.next = prev.next.next

@Override
public E remove(int index) {
rangeCheck(index);

Node<E> node = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
Node<E> last = node(size - 1);
first = first.next;
last.next = first;
}
} else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}

6.2.3修改

@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}

6.2.4查询

	/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);

Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}

return node;
}

@Override
public E get(int index) {
return node(index).element;
}

7.双向循环链表
7.1概念

链表看这篇就够了

双向循环链表的节点不仅包含指向下一个节点的指针(next),还包含指向前一个节点的指针(prev),并且有循环链表的特点,最后一个结点的next指向第一个结点。

当链表只有一个元素时:
链表看这篇就够了

7.2基本操作

与单链表的操作类似,创建一个内部类Node

	private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}

然后创建first和last指针分别指向第一个结点和最后一个结点。

private Node<E> first;
private Node<E> last;

7.2.1添加

链表看这篇就够了
链表看这篇就够了

@Override
public void add(int index, E element) {
rangeCheckForAdd(index);

// size == 0
// index == 0
if (index == size) { // 往最后面添加元素
Node<E> oldLast = last;
last = new Node<>(oldLast, element, first);
if (oldLast == null) { // 这是链表添加的第一个元素
first = last;
first.next = first;
first.prev = first;
} else {
oldLast.next = last;
first.prev = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
prev.next = node;

if (next == first) { // index == 0
first = node;
}
}

size++;
}

7.2.2删除

链表看这篇就够了

public E remove(int index) {
rangeCheck(index);

Node<E> node = node(index);
if (size == 1) {
first = null;
last = null;
} else {
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;

if (node == first) { // index == 0
first = next;
}

if (node == last) { // index == size - 1
last = prev;
}
}

size--;
return node.element;
}

7.2.3修改

@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}


7.2.4查询

/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);

if (index < (size >> 1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}

@Override
public E get(int index) {
return node(index).element;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

链表看这篇就够了

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 链表看这篇就够了
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏