public class Link {
static Node head;
static class Node {
//数据域
public int data;
//指针域，指向下一个节点
public Node next;
public Node(int data) {
this.data = data;
}
}
/**
* 向链表添加数据
*
* @param dataue 要添加的数据
*/
public void addData(int dataue) {
//初始化要加入的节点
Node newNode = new Node(dataue);
if(head == null){
head = newNode;
return;
}
//临时节点
Node temp = head;
// 找到尾节点
while (temp.next != null) {
temp = temp.next;
}
// 已经包括了头节点.next为null的情况了～
temp.next = newNode;
}
/**
* 遍历链表
*
* @param node 节点
*/
public void traverse(Node node) {
//临时节点，从首节点开始
Node temp = node;
while (temp != null) {
System.out.println("节点：" + temp.data);
//继续下一个
temp = temp.next;
}
}
public void traverse() {
traverse(head);
}
/**
* 获取链表的长度
*/
public int linkListLength() {
int length = 0;
//临时节点，从首节点开始
Node temp = head;
// 找到尾节点
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
/**
* 插入节点
*
* @param index 要插入的位置
* @param dataue 要插入的值
*/
public void insertNode( int index, int dataue) {
//首先需要判断指定位置是否合法，
if (index < 1 || index > linkListLength() + 1) {
System.out.println("插入位置不合法。");
return;
}
//临时节点，从头节点开始
Node temp = head;
//记录遍历的当前位置
int currentPos = 1;
//初始化要插入的节点
Node insertNode = new Node(dataue);
while (temp.next != null) {
//找到上一个节点的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一个节点
//将原本由上一个节点的指向交由插入的节点来指向
insertNode.next = temp.next;
//将上一个节点的指针域指向要插入的节点
temp.next = insertNode;
return;
}
currentPos++;
temp = temp.next;
}
}
/**
* 根据位置删除节点
*
* @param index 要删除的位置
*/
public void deleteNode( int index) {
//首先需要判断指定位置是否合法，
if (index < 1 || index > linkListLength() + 1) {
System.out.println("删除位置不合法。");
return;
}
//临时节点，从头节点开始
Node temp = head;
//记录遍历的当前位置
int currentPos = 1;
while (temp.next != null) {
//找到上一个节点的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一个节点
//temp.next表示的是想要删除的节点
//将想要删除的节点存储一下
Node deleteNode = temp.next;
//想要删除节点的下一个节点交由上一个节点来控制
temp.next = deleteNode.next;
return;
}
currentPos++;
temp = temp.next;
}
}
//冒泡排序
public void bubbleSort(){
if(head == null || head.next == null) //链表为空或者仅有单个结点
return ;
Node cur = null, tail = null;
cur = head;
//1->2->3, 第一轮tail为null，循环完是cur是3节点，第二轮循环到3节点退出，此时cur是2节点
while(cur.next != tail){
while(cur.next != tail){
if(cur.data > cur.next.data){
int tmp = cur.data;
cur.data = cur.next.data;
cur.next.data = tmp;
}
cur = cur.next;
}
tail = cur; //下一次遍历的尾结点是当前结点(仔细琢磨一下里面的道道)
cur = head; //遍历起始结点重置为头结点
}
return ;
}
/**
* 找到链表中倒数第k个节点(设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
*
* @param k 倒数第k个节点
*/
public Node findKNode( int k) {
if (k < 1 || k > linkListLength())
return null;
Node p1 = head;
Node p2 = head;
// p2比怕p1快k个节点
for (int i = 0; i < k - 1; i++)
p2 = p2.next;
// 只要p2为null，那么p1就是倒数第k个节点了
while (p2.next != null) {
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
/**
* 删除链表重复数据(跟冒泡差不多，等于删除就是了)
*
*/
public void deleteDuplecate() {
if(head == null || head.next == null) //链表为空或者仅有单个结点
return ;
Node cur = null, tail = null;
cur = head;
//1->2->3, 第一轮tail为null，循环完是cur是3节点，第二轮循环到3节点退出，此时cur是2节点
while(cur.next != tail){
while(cur.next != tail){
if(cur.data == cur.next.data){
cur.next = cur.next.next;
}
cur = cur.next;
}
tail = cur; //下一次遍历的尾结点是当前结点(仔细琢磨一下里面的道道)
cur = head; //遍历起始结点重置为头结点
}
return ;
}
/**
* 查询单链表的中间节点
*/
public Node searchMid() {
Node p1 = head;
Node p2 = head;
// 一个走一步，一个走两步，直到为null，走一步的到达的就是中间节点
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
/**
* 通过递归从尾到头输出单链表
*
* @param head 头节点
*/
public void printListReversely(Node head) {
if (head != null) {
printListReversely(head.next);
System.out.println("节点："+head.data);
}
}
/**
* 实现链表的反转
*
* @param node 链表的头节点
*/
public static Node reverseLinkList(Node node) {
Node prev ;
if (node == null || node.next == null) {
prev = node;
} else {
Node tmp = reverseLinkList(node.next);
node.next.next = node;
node.next = null;
prev = tmp;
}
return prev;
}
public static void main(String[] args) {
Link link = new Link();
link.addData(4);
link.addData(7);
link.addData(3);
link.addData(2);
link.addData(6);
link.addData(4);
System.out.println("链表长度："+link.linkListLength());
link.traverse();
System.out.println("插入节点第四个位置节点5------");
link.insertNode(4,5);
link.traverse();
System.out.println("删除第五个节点------");
link.deleteNode(5);
link.traverse();
System.out.println("冒泡排序------");
link.bubbleSort();
link.traverse();
Node KNode = link.findKNode(2);
System.out.println("倒数第二个节点："+KNode.data);
System.out.println("删除重复数据------");
link.deleteDuplecate();
link.traverse();
Node MidNode = link.searchMid();
System.out.println("中间节点："+MidNode.data);
System.out.println("通过递归从尾到头输出单链表---");
link.printListReversely(head);
System.out.println("反转链表------");
Node reverseNode = reverseLinkList(head);
link.traverse(reverseNode);
}
}
参考：使用递归和非递归方式反转单向链表，Java实现单向链表反转
实现思路
- 递归：从尾部开始处理
- 非递归：从头部开始处理
// 递归方式
public static Node reverse(Node node) {
if (node == null || node.next == null) {
return node;
}
//下一个节点
Node nextNode = node.next;
//当前节点
Node curNode = node;
node.next = null;
Node reverseRest = reverseLinkList(nextNode);
//更新下个节点的next为当前节点
nextNode.next = curNode;
return reverseRest;
}
// 非递归方式
public static Node reverse1(Node node) {
//前一个节点
Node prevNode = null;
//下一个节点
Node nextNode = null;
//当前节点
Node curNode = null;
while (node != null) {
curNode = node;
nextNode = curNode.next;
//更新当前节点的next为前一个节点
curNode.next = prevNode;
//当前节点为下一次循环的前一个节点
prevNode = curNode;
node = nextNode;
}
return prevNode;
}
相关推荐
用java实现了数据结构中的链表，作为新手学习数据结构和java的资料。
JAVA实现链表_双向链表
Java 实现链表 在计算机科学中，链表是一种常用的数据结构，它允许在内存中存储和管理大量的数据。Java 语言提供了多种方式来实现链表，本文将详细介绍 Java 实现链表的方法和技巧。 链表的定义 链表是一种非线性...
标题“试析用Java实现链表数据结构.pdf”所揭示的知识点涵盖了Java编程语言在内存管理和链表数据结构实现方面的深入探讨。描述中提到的“#资源达人分享计划#”可能意味着这篇文章是作为知识分享的一部分，而标签...
### JAVA实现链表知识点详解 #### 一、链表基础概念 链表是一种常见的基础数据结构，用于存储元素集合。在Java中，链表的实现可以是非线性的，具有动态数组的特性，也就是说，链表的大小不需要在创建时指定，可以...
用java实现链表增删改查
使用Java实现链表的基本功能并结合算法题
数据结构，用Java实现链表 private class Node { private String data; private Node next; public Node(String dataPortioin) { data = dataPortioin; next = null; } public Node(String ...
虽然Java没有像C或C++那样的指针，但是通过对象引用，我们完全可以在Java中实现链表数据结构。这种实现方式不仅安全，而且易于理解和操作。通过链表，我们可以高效地处理动态数据集，执行插入、删除等操作，而无需...
Java实现链表中元素的获取、查询和修改方法详解 Java链表是一种重要的数据结构，它可以用来存储和管理数据。在Java中，链表可以通过LinkedList类来实现，但是在实际开发中，我们需要了解如何在链表中获取、查询和...
本篇文章将深入探讨如何使用Java实现链表，以及`LinkedList`类的相关特性和操作。 首先，链表不同于数组，它不连续存储数据。每个元素（节点）包含两部分：数据和指向下一个节点的引用。在Java的`LinkedList`中，每...
链表的Java实现 链表是一种非常重要的数据结构，它的应用非常广泛。在 Java 中，链表可以通过面向对象语言来实现。链表的特点是由一组相互连接的动态分配的结点组成，因此链表适用于进行频繁的修改、插入和删除等...
本篇文章将深入探讨如何使用Java实现链表的创建以及链表反转的过程，同时提供一个可能的调试代码参考。 首先，我们定义一个链表节点类`ListNode`，它包含一个数据域`val`和一个指向下一个节点的引用`next`： ```...
用Java定义一个双向链表，实现链表的基本操作： 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
以下是使用迭代方式实现双向链表反转的Java代码： ```java public void reverse() { if (head == null || head.next == null) { return; } Node current = head; Node previous = null; while (current != ...
接下来，我们需要编写一个方法来实现链表的倒序。该方法接收链表的头结点作为参数，并返回倒序后的新的头结点。实现的逻辑大致分为以下几个步骤： 1. 初始化三个指针：`p`、`q`和`head`。 2. 使用循环逐个反转节点的...
本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现，以及相关的操作，如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先，我们来理解单链表和双向链表的基本概念。单链表是一种线性...