- 浏览: 55457 次
- 性别:
- 来自: 杭州
最新评论
带头结点的单链表实现
不带头结点的单链表实现
public class LinkedList<T> { private Entry<T> head, tail; //头指针,尾指针 private int size; //通过一个变量记录链表长度 public LinkedList() { //生成一个头结点,让头指针和尾指针都指向它 head = tail = new Entry<T>(null); size = 0; } public int size() { return size; } public boolean isEmpty() { return head.next == null; //当头结点的next为空,表明整个链表为空 } public T get(int index) { return current(index).element; } public T set(int index, T element) { Entry<T> entry = current(index); T oldVal = entry.element; entry.element = element; return oldVal; } //默认在原链表尾部添加新的结点 public boolean add(T element) { Entry<T> newEntry = new Entry<T>(element); tail.next = newEntry;//原链表尾指针的next指向新的结点 tail = newEntry;//尾指针向后移动一位,指向新的结点 size++; return true; } public boolean add(int index, T element) { //若索引值和链表长度一样,新结点添加到链表最后位置 if (index == size) return add(element); //得到索引index的前一个结点 Entry<T> preEntry = previous(index); //新结点的next为preEntry的next指向的结点 Entry<T> newEntry = new Entry<T>(element, preEntry.next); //preEntry的next指向新的结点 preEntry.next = newEntry; size++; return true; } public T remove(int index) { //得到索引index的前一个结点 Entry<T> preEntry = previous(index); T oldVal = preEntry.next.element; //如果preEntry的next刚好是最后一个结点,修改tail为preEntry if (preEntry.next == tail) tail = preEntry; preEntry.next = preEntry.next.next; size--; return oldVal; } public void clear() { head.next = null; tail = head; size = 0; } public String toString() { String result = "["; Entry<T> entry = head.next; while (entry != null) { result += entry.element; entry = entry.next; if (entry != null) result += ", "; } return result + "]"; } //获得索引index对应的entry public Entry<T> current(int index) { checkIndexBounds(index); Entry<T> entry = head.next;//从第一个结点开始遍历 int c = 0; while (entry != null && c < index) { entry = entry.next; c++; } return entry; } //获得索引index-1对应的entry public Entry<T> previous(int index) { checkIndexBounds(index); Entry<T> entry = head;//从头结点开始遍历,头指针指向头结点 int c = 0; while (entry.next != null && c < index) { entry = entry.next; c++; } return entry; } private void checkIndexBounds(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("[index: " + index + ", size: " + size + "]"); } //结点对象 private static class Entry<T> { T element; Entry<T> next; public Entry(T element) { this(element, null); } public Entry(T element, Entry<T> next) { this.element = element; this.next = next; } } }
不带头结点的单链表实现
public class LinkedList<T> { private Entry<T> head, tail; private int size; public LinkedList() { head = tail = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return head == null; //头指针为空,表示整个链表为空 } public T get(int index) { return current(index).element; } public T set(int index, T element) { Entry<T> entry = current(index); T oldVal = entry.element; entry.element = element; return oldVal; } public boolean add(T element) { Entry<T> newEntry = new Entry<T>(element); if (head == null) //如果头指针为空,直接将新结点赋值给头指针和尾指针 head = tail = newEntry; else { tail.next = newEntry; //否则,尾指针的next指向新的结点,尾指针后移一位,指向新的结点 tail = newEntry; } size++; return true; } public boolean add(int index, T element) { //若索引值和链表长度一样,新结点添加到链表最后位置 if (index == size) return add(element); //获得索引值为index-1的结点 Entry<T> preEntry = previous(index); Entry<T> newEntry = new Entry<T>(element); if (preEntry == null) { //index=0 直接操作头指针 newEntry.next = head; head = newEntry; } else { //其他情况,用获得的前一个结点完成添加操作 newEntry.next = preEntry.next; preEntry.next = newEntry; } size++; return true; } public T remove(int index) { //获得索引值为index-1的结点 Entry<T> preEntry = previous(index); T oldVal; if (preEntry == null) {//index=0 直接操作头指针 oldVal = head.element; head = head.next; } else { //其他情况,用获得的前一个结点完成移除操作 oldVal = preEntry.next.element; //如果preEntry的next刚好是最后一个结点,修改tail为preEntry if (tail == preEntry.next) tail = preEntry; preEntry.next = preEntry.next.next; } size--; return oldVal; } public void clear() { head = tail = null; size = 0; } public String toString() { String result = "["; Entry<T> entry = head; while (entry != null) { result += entry.element; entry = entry.next; if (entry != null) result += ", "; } return result + "]"; } public Entry<T> current(int index) { checkIndexBounds(index); Entry<T> entry = head; int c = 0; while (entry != null && c < index) { entry = entry.next; c++; } return entry; } public Entry<T> previous(int index) { checkIndexBounds(index); if (index == 0) //索引为0 直接返回null,表明直接用头指针完成操作即可 return null; Entry<T> entry = head; int c = 0; while (entry.next != null && c < index - 1) { entry = entry.next; c++; } return entry; } private void checkIndexBounds(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("[index: " + index + ", size: " + size + "]"); } private static class Entry<T> { T element; Entry<T> next; public Entry(T element) { this(element, null); } public Entry(T element, Entry<T> next) { this.element = element; this.next = next; } } }
发表评论
-
redis安装(windows.exe)
2014-05-21 22:54 735https://github.com/rgl/redis ... -
rabbitMQ安装(windows下)
2014-05-21 22:41 649进入项目下载主页面http://www.rabbitmq.co ... -
实现单线程的断点下载
2014-04-16 09:43 840/** * 实现单线程的断点下载 */ publ ... -
实现一个简易的http模拟器
2014-04-15 15:20 1795/** * http模拟器 * 模拟发送http请求和 ... -
xml学习鉴定
2014-04-09 23:33 838实现招生录取系统中的 ... -
xml学习
2014-04-08 22:47 1470XML:Extensible Markup Langu ... -
HTTP断点续传
2014-03-31 22:13 789http://fenglingcorp.iteye.com/b ... -
java多线程-线程状态转换
2014-03-01 09:20 7941. 新建(new):新创建了一个线程对象。 2. 可 ... -
apt处理自定义annotation
2014-02-19 23:20 1017package annotations; import ... -
跳过UTF-8的BOM
2014-02-14 12:19 1501/** version: 1.1 / 2007-01-25 ... -
java reference
2014-02-09 00:36 672import java.lang.ref.PhantomR ... -
不带头结点的单链表面试汇总
2014-01-24 13:47 1492import java.io.ByteArrayInputSt ... -
带头节点的单链表面试题汇总
2014-01-23 15:12 1027import java.io.ByteArrayInput ... -
单链表面试题之-链表反转
2014-01-15 22:43 1101单链表反转 -------------------- ... -
ClassLoader
2013-11-08 15:57 905public class ClassLoaderTest { ... -
URL和URI
2013-11-08 13:48 512private static void getData ... -
i++和++i
2013-11-06 15:26 522// i = i++ 计算过程 // temp = i; ... -
java 继承 多态
2013-11-06 15:19 800/** 运行结果: A's constructor co ... -
sealing violation
2013-11-03 16:10 3135一般以下两种情况会触发sealing安全异常 1)当被密封(s ... -
hashmap分析
2013-10-30 15:20 691/** hashmap底层维护着一个entry数组,每 ...
相关推荐
在本主题中,我们将探讨如何在Java中实现一个不带头结点的单链表。 首先,我们需要定义链表节点类。一个不带头结点的链表意味着我们不会有一个额外的节点作为列表的起点,第一个节点就是列表的头。以下是一个简单的...
Java实现带头结点的单链表 Java实现带头结点的单链表是一种链式数据结构,链表的...Java实现带头结点的单链表是一种重要的数据结构,它可以用来实现各种数据的存储和管理。通过链表的实现,可以更好地管理和维护数据。
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法。(Java描述)
1.理解数据结构中带头结点单链表的定义和逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现。 4.熟练掌握简单的演示菜单与人机交互设计方法。 二、...
设ha和hb分别是指向两个带头结点的非递减(递增)有序单链表的头指针。要求设计一个算法,将这两个有序链表合并成一个非递增(递减)有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它存储...
给定一个按整数值递增排序的带头结点的动态单链表L,我们需要在链表中插入值为x的结点,保持链表的有序性。为了实现这一操作,我们可以遍历链表,找到适当的位置将新结点插入。以下是一个简单的实现: ```java ...
实际的编程实现可能会根据所使用的编程语言有所不同,例如,C 语言的实现可能需要考虑指针操作,而 Java 或 Python 等高级语言可以使用对象和引用。在提供的 1.c 文件中,可能包含了这个功能的具体 C 语言实现,而 1...
3. 设计和实现二分查找树,以及查找、插入和删除操作。 4. 创建一个简单的散列表,研究冲突解决策略,如开放寻址法和链地址法。 5. 分析和比较不同数据结构的性能,如时间复杂度和空间复杂度。 实验结果截图是对...
单链表(带头结点) 逻辑结构示意图如下 单链表的添加(创建): 1)先创建一个head 头节点,头结点不存放具体的数据, 作用就是表示单链表的头。 2) 后面我们每添加一个节点,就直接加入到 链表的最后。 如果需要...
本篇文章主要介绍了数据结构的几个重要知识点,包括顺序表、单链表、带头结点的单链表等数据结构的算法实现。这些算法涵盖了插入、删除、统计元素个数、求和等操作。 1. 顺序表插入算法: 在顺序表 L 中插入一个...
1. **不带头结点的单链表**: 在这种情况下,链表可能只有一个元素或者为空。头指针直接指向首元素结点。 2. **带头结点的单链表**: 这种设计在首元素结点之前附加了一个头结点。头指针指向这个头结点。 #### 四、头...
**习2.9:建立按升序排序的单链表(不带头结点)** - **题目**:建立一个升序排序的单链表。 - **解答**:在添加新节点时,需要保证节点按升序排列。 **习2.10:实验2.6带头结点的循环双链表类,实现线性表接口** -...
在提供的文件信息中,虽然标题和描述部分未给出具体内容,但是“java 版本循环链表”的标题和部分描述内容暗示了文章内容应该是与Java编程语言实现的循环链表数据结构相关。循环链表是一种常见的数据结构,在计算机...
【习2.9】 建立按升序排序的单链表(不带头结点)。 8 【习2.10】 实验2.6 带头结点的循环双链表类,实现线性表接口。 10 【习2.11】 实验2.5 建立按升序排序的循环双链表。 14 第3章 栈和队列 17 【习3.1】 习3-5 ...
这个压缩包中包含的资料是针对初学者设计的,旨在帮助他们理解并掌握数据结构的基本概念和实现方法,主要使用的编程语言是Java。下面我们将逐一解析每个文档可能涵盖的知识点。 1. **单链表类.doc**: - 单链表:...
给定一个带头结点的单链表,每个结点包含一个整型域 `info` 和指向下一个结点的指针域 `next`。设计一个算法删除单链表中所有重复出现的结点,使得 `info` 域相等的结点只保留一个。 **解决思路**: 通过两个指针...
这里,你需要实现一个带头结点的单链表类`SinglyList<T>`,并提供以下基本操作: 1. 检查列表是否为空(`isEmpty()`) 2. 获取元素(`get(int index)`) 3. 查找元素位置(`indexOf(T key)`) 4. 输出链表元素(`...
7. 循环链表判断:带头结点的循环链表h为空的条件是h->next==h。 8. 无向完全图的边数:n个顶点的无向完全图的边数为n*(n-1)/2。 9. 数组存储:数组M按行优先存储,M[8][5]的起始地址为EA+8*(10*3)+5*3;按列优先...
6. 空链表的判定:不带头结点的单链表为空的条件是head==NULL,而带头结点的单链表为空的条件是head->next==NULL。 7. 最佳存储结构:如果最常用的操作是在最后一个结点之后插入或删除,使用带头结点的双循环链表...
链表主要分为两种类型:带头结点的链表和不带头结点的链表。头结点是一个特殊的节点,它的next域指向链表的第一个实际数据节点。 单链表的反转是一个常见的操作,它将链表中的前后顺序颠倒,使得原链表的最后一个...