1.普通链表的实现
//链表节点类
class LinkedListNode {
int info;
LinkedListNode link;
}
//链表类
public class LinkedListClass {
protected LinkedListNode first, last;
protected int count;
public LinkedListClass() {
first = null;
last = null;
count = 0;
}
public LinkedListClass(LinkedListClass otherList) {
copy(otherList);
}
public void initializeList() {
first = null;
last = null;
count = 0;
}
/* 输出链表 */
public void print() {
LinkedListNode current;
current = first;
while (current != null) {
System.out.println(current.info + " ");
current = current.link;
}
}
/* 链表的长度 */
public int length() {
return count;
}
/* 链表是否为空 */
public boolean isEmptyList() {
return (first == null);
}
/* 检索第一个节点 */
public int front() {
int temp = first.info;
return temp;
}
/* 检索最后一个节点 */
public int back() {
int temp = last.info;
return temp;
}
/* 正向构建链表，向链表尾插入节点 */
public void insertlLast(int newIntem) {
LinkedListNode newNode;
newNode = new LinkedListNode();
newNode.info = newIntem;
newNode.link = null;
if (first == null) {
first = newNode;
last = newNode;
} else {
last.link = newNode;
last = newNode;
}
count++;
}
/* 反向构建链表，向链表头部插入新节点 */
public void insertFirst(int newItem) {
LinkedListNode newNode;
newNode = new LinkedListNode();
newNode.info = newItem;
newNode.link = first;
first = newNode;
if (last == null)// 如果链表为空，新插入的newNode也是链表中的最后一个节点
last = newNode;
count++;
}
/* 复制链表 */
private void copy(LinkedListClass otherList) {
LinkedListNode newNode;
LinkedListNode current;
first = null;
if (otherList.first == null) {
first = null;
last = null;
count = 0;
} else {
count = otherList.count;
current = otherList.first;
first = new LinkedListNode();
first.info = current.info;
first.link = null;
last = first;
current = current.link;
while (current != null) {
newNode = new LinkedListNode();
newNode.info = current.info;
newNode.link = null;
last.link = newNode;
last = newNode;
current = current.link;
}
}
}
/* 拷贝链表的方法 */
public void copyList(LinkedListClass otherList) {
if (this != otherList)
copy(otherList);
}
}
2.有序链表的实现
*有序链表*/
public class OrderedLinkedList extends LinkedListClass {
public OrderedLinkedList(){
super();
}
public OrderedLinkedList(OrderedLinkedList otherList){
super(otherList);
}
/*
* 搜索链表 1.将搜索项与链表中的当前节点相比较，如果当前节点的info大于等于serachItem，则停止搜索 否则，就把下一个节点变成当前节点。
*/
public boolean search(int searchItem) {
LinkedListNode current;
boolean found;
current = first;
found = false;
while (current != null && !found) {
if (current.info >= searchItem)
found = true;
else
current = current.link;
}
if (found)
found = (current.info == searchItem);
return found;
}
/*
* 插入节点
* 1. 链表最初为空
* 2. 链表为非空，且新元素小于链表中最小的元素
* 3. 链表为非空，且待插入的元素比链表中的第一个元素大，改元素应插入链表中的某个位置
* a. 新项大于链表中的所有元素，插入链表末尾
* b. 新项插入链表中间的某个位置
*/
public void insertNode(int insertItem) {
LinkedListNode current;
LinkedListNode trailCurrent;
LinkedListNode newNode;
boolean found;
newNode = new LinkedListNode();
newNode.info = insertItem;
newNode.link = null;
if (first == null) {
first = newNode;
count++;
} else {
trailCurrent = first;
current = first;
found = false;
while (current != null && !found)
if (current.info >= insertItem)
found = true;
else {
trailCurrent = current;
current = current.link;
}
if (current == first) {
newNode.link = first;
first = newNode;
count++;
} else {
trailCurrent.link = newNode;
newNode.link = current;
count++;
}
}
}
/*
* 删除节点
* 1. 链表为空
* 2. 待删除项的元素包含在链表的第一个节点中，须调整first的值
* 3. 待删除项在链表的摸个位置
* 4. 链表为非空，待删除的节点不在链表中
*/
public void deleteNode(int deleteItem) {
LinkedListNode current;
LinkedListNode trailCurrent;
boolean found;
if (first == null)// Case 1
System.out.println("Error!");
else {
if (first.info == deleteItem) {// Case 2
first = first.link;
count--;
} else {
found = false;
trailCurrent = first;
current = first.link;
while (current != null && !found) {
if (current.info >= deleteItem)
found = true;
else {
trailCurrent = current;
current = current.link;
}
}
if (current == null)// Case 4
System.out.println("deleteItem is not in the list!");
else if (current.info == deleteItem) {
if (first == current) {// Case 2
first = first.link;
count--;
} else {// Case 3
trailCurrent.link = current.link;
count--;
}
} else
// Case 4
System.out.println("deleteItem is not in the list!");
}
}
}
}
3.无序链表的实现
/*无序链表*/
public class UnorderedLinkedList extends LinkedListClass {
public UnorderedLinkedList(){
super();
}
public UnorderedLinkedList(UnorderedLinkedList otherList){
super(otherList);
}
/* 查找节点 */
public boolean search(int searchItem) {
LinkedListNode current;
boolean found;
current = first;
found = false;
while (current != null && !found) {
if (current.info == searchItem)
found = true;
else
current = current.link;
}
return found;
}
/* 删除节点
* 1. 链表为空
* 2. 链表非空，且删除的节点是第一个节点
* a. 链表只有一个节点
* b. 链表含有多个节点
* 3. 待删除的节点不是第一个节点
* a. 待删除的节点不是最后一个节点
* b. 待删除节点是最后一个节点
* 4. 待删除节点不在链表中
* */
public void deleteNode(int deleteItem) {
LinkedListNode current;
LinkedListNode trailCurrent;
boolean found;
if (first == null)
System.out.println("Error!");
else {
if (first.info == deleteItem) {
first = first.link;
if (first == null)
last = null;
count--;
} else {
found = false;
trailCurrent = first;
current = first.link;
while (current != null && !found) {
if (current.info == deleteItem)
found = true;
else {
trailCurrent = current;
current = current.link;
}
}
if (found) {
count--;
trailCurrent.link = current.link;
if (last == current)
last = trailCurrent;
} else
System.out.println("deletItem is not in the list!");
}
}
}
}
4.双向链表的实现
/*双向链表*/
class DoublyLinkedNode {
int info;
DoublyLinkedNode next;
DoublyLinkedNode back;
}
public class DoublyLinkedClass {
int count;
DoublyLinkedNode first;
DoublyLinkedNode last;
public DoublyLinkedClass() {
first = null;
last = null;
count = 0;
}
public void initializeList() {
first = null;
last = null;
count = 0;
}
/* 链表是否为空 */
public boolean isEmpty() {
return (first == null);
}
/* 链表的长度 */
public int length() {
return count;
}
/* 输出链表 */
public void print() {
DoublyLinkedNode current;
current = first;
while (current != null) {
System.out.println(current.info + " ");
current = current.next;
}
}
/* 反向输出链表 */
public void reversePrint() {
DoublyLinkedNode current;
current = last;
while (current != null) {
System.out.println(current.info + " ");
current = current.back;
}
}
/* 搜索链表 */
public boolean search(int searchItem) {
boolean found;
DoublyLinkedNode current;
found = false;
current = first;
while (current != null && !found)
if (current.info >= searchItem)
found = true;
else
current = current.next;
if (found)
found = (current.info == searchItem);
return found;
}
/*
* 插入节点
* 1. 在一个空链表中插入
* 2. 在一个非空链表的开始处插入
* 3. 在一个非空链表的末尾处插入
* 4. 在一个非空链表的中间某个位置插入
*/
public void insertNode(int insertInterm) {
DoublyLinkedNode current;
DoublyLinkedNode trailCurrent = null;
DoublyLinkedNode newNode;
boolean found;
newNode = new DoublyLinkedNode();
newNode.info = insertInterm;
newNode.next = null;
newNode.back = null;
if (first == null) {
first = newNode;
last = newNode;
count++;
} else {
found = false;
current = first;
while (current != null && !found) {
if (current.info >= insertInterm)
found = true;
else {
trailCurrent = current;
current = current.next;
}
}
if (current == first) {
first.back = newNode;
newNode.next = first;
first = newNode;
count++;
} else {
if (current != null) {
trailCurrent.next = newNode;
newNode.back = trailCurrent;
newNode.next = current;
current.back = newNode;
} else {
trailCurrent.next = newNode;
newNode.back = trailCurrent;
last = newNode;
}
count++;
}
}
}
/*
* 删除节点
* 1. 链表为空
* 2. 待删除项是链表中的第一个节点，须改变first的值
* 3. 待删除项在链表中的某个位置
* 4. 待删除项不再链表中
*/
public void deleteNode(int deleteItem) {
DoublyLinkedNode current;
DoublyLinkedNode trailCurrent;
boolean found;
if (first == null)
System.err.println("Cannot delete from an empty list.");
else if (first.info == deleteItem) {
current = first;
first = first.next;
if (first != null)
first.back = null;
else
last = null;
count--;
} else {
found = false;
current = first;
while (current != null && !found)
if (current.info >= deleteItem)
found = true;
else
current = current.next;
if (current == null)
System.out.println("deleteItem is not in the list!");
else if (current.info == deleteItem) {
trailCurrent = current.back;
trailCurrent.next = current.next;
if (current.next != null)
current.next.back = trailCurrent;
if (current == last)
last = trailCurrent;
count--;
} else
System.out.println("deleteItem is not in the list!");
}
}
}
分享到：
相关推荐
全书内容浅显易懂，利用大量且丰富的图示与范例， 详解复杂的抽象理论，从最基本的数据结构概念开始 说明，再以Java工具加以诠释阵列结构、堆栈、链表 、队列、排序、查找等重要的概念，引领读者抓住重 点轻松进入...
Java中的链表数据结构，尤其是单链表，提供了一种灵活的存储和操作数据的方式，尤其适合需要频繁插入和删除元素的情况。链表的实现涉及节点类的设计，包括数据域和指针域，以及链表类的构建，包括头节点和元素计数。...
数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍：http://blog.csdn.net/z740852294/article/details/77369439
链表是一种常见的线性数据结构，它通过节点之间的连接来表示数据项。与数组不同，链表中的元素不必存储在连续的内存空间中。每个节点包含两部分：数据部分（用于存储实际的数据）和指针部分（用于指向下一个节点的...
链表 链表_使用JAVA语言实现链表数据结构
在本文中，我们将深入探讨与链表相关的三个Java编程题目，这些都是...这些技巧对于理解和操作链表数据结构至关重要，是解决链表相关问题的基础。在实际编程面试和工作中，掌握这些技能可以有效地处理链表相关的问题。
实现这些链表数据结构时，通常会定义一个List接口，它定义了对链表进行操作的一系列方法，如add、remove、get等。然后，我们分别实现SequentialList（顺序表）、SingleLinkedList（单链表）和DoubleLinkedList（双...
数据结构-Java中实现一个简单的链表结构，通过定义一个节点类（Node），然后定义一个链表类（LinkedList）来管理节点，简单易懂，适合初学数据结构的同学掌握基本数据结构的使用实现原理。
链表是一种重要的线性数据结构，它与数组相比具有独特的特性和优势。链表由一系列节点构成，每个节点包含两部分：数据元素和指向下一个节点的引用。这种结构允许链表在内存中不连续分布，提供了动态扩展和收缩的能力...
Java数据结构 线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构
《数据结构（Java版本）》这本书正是为此目的而编写，旨在将理论与实际编程相结合，通过Java语言来实现各种经典的数据结构。 首先，书中的基础部分会介绍数据结构的基本概念，如数组、链表、栈和队列。数组是最基本...
### 数据结构之链表 #### 一、链表概述 链表是一种常用的数据结构，在计算机科学领域占有极其重要的地位。链表与数组等其他数据结构相比，在某些操作上具有显著的优势，尤其是在动态调整大小和频繁插入删除的情况...
链表是一种基础且重要的数据结构，它在计算机科学和编程，尤其是Java中有着广泛的应用。与数组不同，链表中的元素并不在内存中连续存储，而是通过节点间的引用（或称为指针）来连接。每个节点包含两部分：数据域，...
Java是一种广泛使用的面向对象的编程语言，具有丰富的库支持，使得在Java中实现数据结构变得既方便又强大。在清华大学出版社出版的朱站立编著的《数据结构》一书中，作者深入浅出地讲解了数据结构的基本概念、设计与...
本资料集专注于数据结构的第六章内容，特别是关于二叉树及其二叉链表存储结构的讲解。二叉树是一种特殊的树结构，每个节点最多只有两个子节点，通常分为左子节点和右子节点。这种结构广泛应用于搜索、排序、文件系统...
在本项目中，“数据结构链表演示（java swing）”利用了Java Swing库来创建一个图形用户界面（GUI），直观地展示链表和堆栈的操作。 Java Swing是Java AWT（Abstract Window Toolkit）的一个扩展，提供了丰富的组件...
线性表是最基本的数据结构之一，可以被视为一种元素序列，每个元素都具有一个唯一的前驱和后继。线性表可以通过数组或链表来实现。 #### 数组 数组是一种简单的线性表实现方式，它可以快速访问任意位置的元素，但...
《计算机科学丛书·数据结构从应用到实现(Java版)》系统地介绍了数据结构以及数据结构与对象之间的联系。主要内容包括：算法效率的输入规模、阶和大O，数据结构的无序和有序列表，队列和栈基于数组和链表的设计实例...