今天学习了链表的相关知识，并在此基础上写了一个自定义的双向结点类和链表类。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的结点之间的引用链接实现的。相比于线性表顺序结构，链表比较方便插入和删除操作。
数组在定义时是在内存中开辟连续的一块区域，而链表则是不固定的，所以在访问时数组更加高效。但是数组必须在定义时就指定大小，所以很有可能造成内存的浪费。还有数组只需要在栈中分配空间，方便快捷。而链表还需要使用到堆中的空间。
下面是自定义的双向结点类
public class LLNode {
private Object obj;
private LLNode child = null;
private LLNode parent = null;
/**
* 它的构造方法
*/
public LLNode(Object obj) {
this.obj = obj;
}
public LLNode getChild() {
return child;
}
public void setChild(LLNode child) {
this.child = child;
}
public LLNode getParent() {
return parent;
}
public void setParent(LLNode parent) {
this.parent = parent;
}
public Object getObj() {
return obj;
}
}
下面是自定义的双向链表类
public class LinkList {
private static LLNode head = null;
private LLNode tail = null;
/**
* 双向链表的构造方法
*/
public LinkList() {
}
/**
* 重写构造方法，创建链表时传入根结点
*/
public LinkList(Object obj) {
head = new LLNode(obj);
tail = head;
}
/**
* 向链表最后添加元素
*
* @param obj
* 添加的元素
*/
public void add(Object obj) {
LLNode node = new LLNode(obj);
if (head == null) {
head = new LLNode(obj);
tail = head;
} else {
tail.setChild(node);
node.setParent(tail);
tail = node;
}
}
/**
* 重写添加的方法 在指定位置添加
*
* @param obj
* 添加的元素
* @param index
* 添加的位置(下标值)
*/
public void add(Object obj, int index) {
LLNode node = new LLNode(obj);
if (index < 0 || index > size()) {// 如果越界
throw new RuntimeException("越界！可添加的范围为：0~" + size() + ".");
} else if (head == null) {// 如果没有开始结点
head = node;
tail = head;
} else if (index == 0) {// 如果插入到链表开头
node.setChild(head);
head.setParent(node);
head = node;
} else if (index == size()) {// 如果插入到链表结尾
add(obj);
} else {
int i = 0;
LLNode current = head;
// 找到位置
while (i != index) {
current = current.getChild();
i++;
}
LLNode fNode = current.getParent();
fNode.setChild(node);
node.setParent(fNode);
node.setChild(current);
current.setParent(node);
}
}
/**
* 替换指定下标处得元素
* @param obj 给予替换的元素
* @param index 指定的下标
*/
public void set(Object obj, int index){
LLNode node = new LLNode(obj);
if (index < 0 || index > size()) {// 如果越界
throw new RuntimeException("越界！可添加的范围为：0~" + size() + ".");
} else if (head == null) {// 如果没有开始结点
System.out.println("没有可以替换的位置，因为它是空链表！");
} else if (index == 0) {// 如果替换到链表开头
node.setChild(head.getChild());
head.getChild().setParent(node);
head = node;
} else if (index == size()) {// 如果替换到链表结尾
node.setParent(tail.getParent());
tail.getParent().setChild(node);
tail = node;
} else {
int i = 0;
LLNode current = head;
// 找到位置
while (i != index) {
current = current.getChild();
i++;
}
LLNode pNode = current.getParent();
LLNode cNode = current.getChild();
pNode.setChild(node);
node.setParent(pNode);
node.setChild(cNode);
cNode.setParent(node);
}
}
/**
* 返回此链表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1
* @param obj 指定的元素
* @return 返回此列表中首次出现的指定元素的下标值
*/
public int indexOf(Object obj){
LLNode current = head;
// 找到位置
int i;
for(i = 0;i<size();i++){
if(current.getObj() == obj){
break;
}
if(i==(size()-1)){
return -1;
}
current = current.getChild();
}
return i;
}
/**
* 移除链表中的一个结点
*
* @param obj
* 移除此元素的节点
* @return 返回表示是否移除
*/
public boolean remove(Object obj) {
LLNode current;
if (head.getObj() == obj) {
current = head.getChild();
current.setParent(null);
head = current;
return true;
} else if (tail.getObj() == obj) {
current = tail.getParent();
current.setChild(null);
tail = current;
return true;
} else {
current = head.getChild();
// 找到位置
for(int i = 0;i<size();i++){
if(current.getObj() == obj){
break;
}
if(i==(size()-1)){
return false;
}
current = current.getChild();
}
LLNode cnode = current.getChild();
LLNode pnode = current.getParent();
pnode.setChild(cnode);
cnode.setParent(pnode);
return true;
}
}
/**
* 移除链表中的一个元素，并返回它
*
* @param index
* 指定的下标位置
* @return 返回这个指定位置的元素
*/
public Object remove(int index) {
LLNode current ;
if(size() == 0){
System.out.println("链表中没有元素，无法移除！");
return null;
}else if (index < 0 || index > size()) {// 如果越界
throw new RuntimeException("越界！可移除的范围为：0~" + size() + ".");
}else if(index == 0){//如果指定位置在开头
LLNode temp = head;
current = head.getChild();
current.setParent(null);
head = current;
return temp.getObj();
}else if(index == size()){//如果指定位置在结尾
LLNode temp = tail;
current = tail.getParent();
current.setChild(null);
tail = current;
return temp.getObj();
}else{
current = head;
int i=0;
while(i != index){
i++;
current = current.getChild();
}
LLNode cnode = current.getChild();
LLNode pnode = current.getParent();
pnode.setChild(cnode);
cnode.setParent(pnode);
return current.getObj();
}
}
/**
* 移除链表中所有元素
*/
public void removeall() {
head.setChild(null);
tail.setParent(null);
head = null;
tail = head;
}
/**
* 判断链表长度的方法
*
* @return 返回链表的长度
*/
public int size() {
int i = 0;
LLNode current = head;
while (current != null) {
current = current.getChild();
i++;
}
return i;
}
/**
* 得到指定下标的元素，但不在链表中移除它
* @param index 指定的下标位置
* @return 返回该元素
*/
public Object get(int index){
if(size() == 0){
System.out.println("链表中没有元素，无法得到！");
return null;
}else if (index < 0 || index > size()) {// 如果越界
throw new RuntimeException("越界！可得到的范围为：0~" + size() + ".");
}else{
LLNode current = head;
int i=0;
while(i != index){
i++;
current = current.getChild();
}
return current.getObj();
}
}
/**
* 从此结点向下遍历的方法
*
* @param node
* 给予的起始结点
*/
public void printfromHead(LLNode node) {
if (node == null) {
System.out.println("链表为空！");
} else {
System.out.println(node.getObj());
if (node.getChild() != null) {
LLNode current = node.getChild();
printfromHead(current);
}
}
}
/**
* 从此结点向上遍历的方法
*
* @param node
* 给予的起始结点
*/
public void printfromTail(LLNode node) {
if (node == null) {
System.out.println("链表为空！");
} else {
System.out.println(node.getObj());
if (node.getParent() != null) {
LLNode current = node.getParent();
printfromTail(current);
}
}
}
/**
* 遍历打印链表的方法
*
* @param node
* 给予的起始结点
*/
public void printList(LLNode node) {
if (node == null) {
System.out.println("链表为空！");
} else {
// 开始向上遍历
if (node.getParent() != null) {
System.out.println("----开始向上遍历----");
LLNode current = node;
printfromTail(current);
} else {
System.out.println("已是根节点，无法向上遍历");
}
// 开始向下遍历
if (node.getChild() != null) {
System.out.println("----开始向下遍历----");
LLNode current = node;
printfromHead(current);
} else {
System.out.println("已是尾节点，无法向下遍历");
}
}
}
}
分享到：
相关推荐
在Java中，双向链表可以使用内置的`java.util.LinkedList`类实现，但要实现有序且非循环的特性，可能需要自定义链表节点类，并添加额外的排序逻辑。例如： ```java class Node { int data; Node prev; Node next...
下面我们将详细讲解如何实现一个自定义的Java双向链表，并参考提供的`LinkNode.java`文件来理解其内部机制。 首先，我们需要定义一个表示链表节点的类`LinkNode`。这个类通常包含三个属性：存储数据的`data`字段、...
《2022年Java语言中链表和双向链表Java教程》 链表作为一种基础且重要的数据结构，广泛应用于编程领域，特别是在Java语言中。虽然Java不直接提供指针，但通过对象引用，我们可以轻松地实现链表的构建。在Java中，...
在计算机科学中，双向链表是一种特殊的链式数据结构，它允许我们在列表的任一位置高效地进行插入和删除...然而，理解如何自定义实现双向链表有助于深入理解数据结构和算法，对于提升编程技能和解决问题的能力大有裨益。
在Java中实现双向链表，我们可以创建一个名为`Node`的类来表示链表节点，其中包含`data`字段用于存储数据，`prev`字段用于存储前驱节点的引用，`next`字段用于存储后继节点的引用。接下来，我们需要一个`Doubly...
`CList2`可能添加了双向链表的功能，每个节点不仅有指向下一个节点的指针，还有指向前一个节点的指针。这允许更灵活的插入和删除操作，同时在遍历时可以从两个方向进行。 8. **JavaScript, C 和 C++ 版本**： ...
在Java中，LinkedList的节点类是Node，它包含了三个字段：data（存储数据）、next（指向下一个节点）和prev（在双向链表中指向前一个节点）。当我们使用LinkedList时，可以通过addFirst()、addLast()、add()、remove...
7. **优化**：为了提高效率，可以使用双向链表，这样可以从头或尾部方便地添加和删除节点。此外，可以考虑使用优先队列（如Java的`PriorityQueue`），其内部已经实现了最小堆，可以快速找到最近的任务。 在J2ME...
本篇将深入探讨Java中的链表及其自定义实现，同时也会涉及双向链表和链表堆栈的实现。 首先，让我们了解链表的基本概念。链表由一系列节点组成，每个节点包含两个部分：数据域（存储元素）和指针域（指向下一个节点...
本压缩包提供的"自定义实现常用数据结构 - java版代码.rar"聚焦于几个关键的数据结构，包括HashMap、LinkedHashMap以及与之相关的红黑树。下面我们将深入探讨这些核心知识点。 首先，HashMap是Java中最常用的一种...
在Java中，我们可以自定义一个`SongNode`类来表示链表中的节点，它包含歌曲信息以及prev和next指针。然后，创建一个`Jukebox`类作为链表的容器，提供插入、删除、查找和播放控制等方法。 1. `SongNode`类：包含歌曲...
链表分为单向链表和双向链表，其中单向链表只能向前遍历，而双向链表可以向前或向后遍历。 1. **链表的基本操作**： - **创建链表**：首先需要定义一个节点类，包含数据和指向下一个节点的引用。然后创建头节点，...
如果链表需要支持双向遍历，可以改用双向链表，并在节点中添加一个指向前一个节点的引用。 总之，这个Java实例展示了如何使用链表数据结构，包括节点的定义、链表的遍历以及基本操作。通过扩展这些基础，可以构建更...
在Java中，链表可以自定义为一个类，包含节点类（Node）和链表类（LinkedList）。节点类可能包含数据字段和指向下一个节点的引用，链表类则包含头部节点和各种操作方法，如insert()、delete()和search()。通过阅读和...
双向链表的优势在于可以从任一方向遍历，同时支持双向插入和删除操作。 接下来是链表操作的API。Linux内核提供了以下关键函数： 1. `INIT_LIST_HEAD(list)`: 初始化一个空链表。将`list`的`next`和`prev`指针设置...
链表可以分为单链表、双向链表和环形链表等类型。 在这个学生成绩管理系统中，我们很可能会使用单链表，因为它的实现相对简单。链表的头节点通常用于指示链表的起始位置，而尾节点则指向null，表示链表的结束。 接...
在Java中，双向链表的实现通常涉及到自定义一个节点类，该类包含三个属性：数据、指向下一个节点的引用和指向前一个节点的引用。节点类的结构可能如下： ```java public class Node { int data; Node next; Node...
在Java编程语言中，"MaQiaoHashArryListMap"是一个自定义的数据结构实现，它结合了数组、链表和哈希表的特点，形成一个有序的双向链表。这个数据结构通常用于提供高效的数据存储和检索服务，尤其是在对元素顺序有...
对于无序链表，还可以设计一个自定义的数据结构，例如双向链表，其中每个节点包含一个值和一个计数器。遍历原链表时，遇到相同值的节点就增加计数器，否则插入新的节点。最后返回的链表只保留计数器大于1的节点。...
本资源包含四个核心的数据结构实现：堆、栈、单链表和双链表，全部使用 Java 语言编写，并且带有详细的注释，非常适合初学者学习和理解。 首先，让我们逐一探讨这些数据结构及其在Java中的实现： 1. **堆**： 堆...