概念:
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,
分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,
都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
实现方式:构造一个常驻内存的头节点引用,然后头节点的上一个节点是最后一个节点,最后
一个节点的下一个是头节点。其他的每个节点都有上下节点的引用。最少有一个头节点
操作:构造链表,销毁链表,计算元素个数,返回链表中指定链表中元素的值,插入元素,删除元素
代码:
package com.alg.link;
import java.util.Iterator;
//双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,
//分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,
//都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
//链表的操作有:构造链表,销毁链表,计算元素个数,返回链表中指定链表中元素的值,插入元素,删除元素
public class DoubleWayLinkedList<T> extends BaseLinkedList<T>
{
transient Link<T> voidLink;
public DoubleWayLinkedList()
{
voidLink = new Link<T>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
// 向尾部添加
@Override
public void add(T object)
{
Link<T> oldLast = voidLink.previous;
// 末尾的上一个是最后一下,下一个是第一个
Link<T> newLink = new Link<T>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
modCount++;
size++;
}
@Override
public void clear()
{
if (size > 0)
{
size = 0;
voidLink.next = voidLink;
voidLink.previous = voidLink;
modCount++;
}
}
@Override
public T get(int location)
{
if (0 <= location && location < size)
{
Link<T> link = voidLink;
if (location < (size / 2))
{
for (int i = 0; i <= location; i++)
{
link = link.next;
}
}
else
{
for (int i = size; i > location; i--)
{
link = link.previous;
}
}
return link.data;
}
return null;
}
// 移除某个元素
@Override
public T remove(int location)
{
if (0 <= location && location < size)
{
Link<T> link = voidLink;
if (location < (size / 2))
{
for (int i = 0; i <= location; i++)
{
link = link.next;
}
}
else
{
for (int i = size; i > location; i--)
{
link = link.previous;
}
}
Link<T> previous = link.previous;
Link<T> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
return null;
}
// 可以加入空的数据,所以有object为null的移除,而且移的是第一个数据为null的
@Override
public boolean remove(Object object)
{
Link<T> link = voidLink.next;
if (object != null)
{
while (link != voidLink && !object.equals(link.data))
{
link = link.next;
}
}
else
{// 如果data为null,则碰到了第一个空数据
while (link != voidLink && link.data != null)
{
link = link.next;
}
}
if (link == voidLink)
{
return false;
}
Link<T> next = link.next;
Link<T> previous = link.previous;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return true;
}
@Override
public int size()
{
return size;
}
public Iterator<T> iterator()
{
return new SimpleIterator();
}
}
分享到:
相关推荐
链表是一种基础且重要的数据结构,它在计算机科学和编程中扮演着至关重要的角色,特别是在算法和数据结构的学习中,LeetCode 是一个很好的实践平台。本笔记将深入探讨 LeetCode 中涉及的链表相关问题,旨在帮助你...
在Java中,LinkedList的节点类是Node,它包含了三个字段:data(存储数据)、next(指向下一个节点)和prev(在双向链表中指向前一个节点)。当我们使用LinkedList时,可以通过addFirst()、addLast()、add()、remove...
本笔记主要涵盖了从第一章到第六章关于数据结构和Java语言的相关知识点。 第一章介绍了数据结构的基本概念,包括面向对象的特性如对象、继承和多态,对比了C++和Java中的指针差异。在Java中,垃圾回收机制自动管理...
进一步学习,可以研究双向链表,它允许在节点的前后进行插入和删除,提高了操作的灵活性。循环链表则形成一个闭合的环,可以简化某些循环操作。 总之,链表是数据结构的基础,理解和熟练运用链表对于提升编程技能...
- `LinkedList`:底层为双向链表,适合频繁插入和删除操作。 - `Vector`:线程安全的`ArrayList`版本。 - `Stack`:继承自`Vector`,模拟栈结构。 **1.6 Set接口** - **特点**:无序且不允许重复元素。 - **...
本压缩包“链表树-复合数据结构应用实例.zip”显然是针对大学生C/C++/JAVA/Python数据结构学习的资源集合,涵盖了这些编程语言的数据结构实现和实践。 首先,让我们深入了解链表。链表是一种线性数据结构,与数组...
《恋上数据结构》的学习笔记涵盖了第一季和第二季的内容,旨在帮助初学者从零开始全面掌握Java实现的数据结构。在这个压缩包中,尽管具体的文件名“dfadfasdkj”并未提供足够的信息,我们可以推测它可能包含了一系列...
- **数组**:Java中的数组是一种存储固定数量同类型元素的数据结构,理解其创建、访问和操作方法至关重要。 2. **面向对象编程**: - **类与对象**:Java是一种面向对象的语言,类是对象的模板,对象是类的实例。...
以下是对"CoreJava_day15"学习笔记中可能涉及的一些关键知识点的详细解释: 1. **异常处理**: - 异常是程序运行时出现的错误,Java通过Exception类及其子类来表示这些错误。在Java中,异常处理使用try-catch-...
- 数组是用来存储相同类型元素的一种数据结构。 - 数组的长度固定,在创建时确定。 - 数组元素可以通过索引访问,索引从0开始。 - **字符串** - String类用于表示不可变的字符序列。 - StringBuilder和...
在Java编程语言中,数据结构是程序设计的基础,它决定了如何有效地存储和处理数据。本篇笔记主要讨论了几个关键的数据结构,包括LinkedList、ArrayList以及HashSet,并通过实例展示了它们的用法。 首先,LinkedList...
### Java入门学习笔记 #### 一、Java特点与运行原理 **1.1 Java特点** - **简单性:** Java的设计使得它易于学习且避免了许多传统编程语言中存在的复杂性。 - **面向对象:** Java是一种纯面向对象的语言,支持...
数据结构与算法是计算机科学的基础,对于任何...这个压缩包中的学习笔记和资料可以帮助大学生深入理解这些概念,并通过Java实践提升编程能力。无论你是初学者还是有经验的开发者,这些资源都将是你提升技能的宝贵财富。
### Java私塾学习笔记整理 #### 第一章:Java入门 **一、Java是什么?** Java是一种广泛使用的高级编程语言,由Sun Microsystems于1995年推出。它旨在为跨平台开发提供一种通用的语言环境,使开发者能够在任何...
本学习笔记由黑马程序员提供,旨在帮助初学者深入理解Java中的集合框架及其使用方法。 首先,我们来探讨“集合”的基本概念。在Java中,集合是一个对象容器,可以容纳多个元素,这些元素可以是任意类型的数据。Java...
理解并熟练掌握这些基本操作对于理解和应用更复杂的数据结构,如双向链表、循环链表、链表栈和链表队列至关重要。同时,它们也是解决算法问题的基础,比如在面试中常见的链表相关问题。因此,对于任何想要进入IT行业...
CoreJava_day11的学习笔记主要涵盖了集合框架,特别是关于List、Set和Map接口,以及ArrayList、Vector和LinkedList等具体实现类的知识点。 首先,集合框架是用来存放对象的对象,它提供了一组接口和类,使得我们...
数组是Java中最基本的数据结构,用于存储相同类型的元素序列。创建数组时需要指定元素类型和大小,一旦创建,大小不可变。数组提供了下标访问元素(通过索引)的方式,索引从0开始。数组操作包括初始化、赋值、遍历...