本帖最后由 卡哇伊伊 于 2019-2-27 15:58 编辑
概述
借用知乎网友的一句话：如果说 Java 是自动档轿车，C 就是手动档吉普。数据结构呢？是变速箱的工作原理。你
完全可以不知道变速箱怎样工作，就把自动档的车子从 A 开到 B，而且未必就比懂得的人慢。写程序这件事，和开
车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造
车。但若你此生在编程领域还有点更高的追求，数据结构是绕不开的课题。
数据结构中有许多种类型，而且实现的语言也有C 也有java.今天我们来讲讲 单链表的java实现添加节点。
单链表概述
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点
来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单
元，指针就是连接每个结点的地址数据。
单链表的实现原理
![]()
说明：在单链表中，我们定义一个节点Node 包括两个部分：元数据和下一个节点的地址。节点和节点之间 通过
next(即下一个节点的地址)来进行关联，这样就形成了一个链式结构。我们很轻易的就能从头（head）结点一直遍
历到最后边的节点。这种结构有点像铁锁一样环环相扣。
单链表的 java实现
实现数据结构的语言可以有很多，这里我们介绍使用java语言来实现。
实现添加向链表中添加节点的步骤
- 定义单链表对象并在内部定义一个节点对象 Node
- 实现向单链表对象中添加节点的功能
- 测试
定义单链表对象
[AppleScript] 纯文本查看 复制代码 package com.itheima.link;
/**
* 单列表
*
* @title SingleLink.java
* <p>
* description
* </p>
* <p>
* company: www.itheima.com
* </p>
* @author 三国的包子
* @version 1.0
*
*
*/
public class SingleLink {
// 结点对象
class Node {
Object data;// 数据
Node next;// 下一个节点的地址引用
// 构造函数 获取数据
public Node(Object data) {
this.data = data;
}
}
Node head;// 表示链表的头结点
}
在SingleLink中增加添加节点的方法
[AppleScript] 纯文本查看 复制代码 /**
* 从尾部添加一个节点
*
* @param data
* 要添加的节点的数据
*/
public void add(Object data) {
// 1.构建一个节点对象
Node node = new Node(data);
if (head == null) {
// 2.判断链表中是否为空 如果为空 则新增的节点变成头节点
head = node;
} else {
// 3.如果链表不为空，则需要查询到尾部节点
Node rear = findRearNode();
// 4.向尾部节点添加一个节点
rear.next = node;// rear肯定不为空
}
}
/**
* 找到尾部节点
*
* @return
*/
private Node findRearNode() {
// 从头开始遍历
// 1.定义一个临时变量 让其等于头
Node temp = head;
while (temp != null) {// 如果不等于空继续遍历
if (temp.next == null) {// 如果接的next的属性为空说明 该节点为尾部节点
break;// 跳出循环
}
temp = temp.next;// 遍历下一个
}
return temp;
}
重写toString 方法用于测试
[AppleScript] 纯文本查看 复制代码 // 重写方法 打印数据
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer("[");
// 遍历
Node temp = head;
while (temp != null) {
if (temp.next == null) {
stringBuffer.append(temp.data);
break;
} else {
stringBuffer.append(temp.data + ",");
}
temp = temp.next;
}
stringBuffer.append("]");
return stringBuffer.toString();
}
测试
[AppleScript] 纯文本查看 复制代码 public class TestLink {
public static void main(String[] args) {
SingleLink singleLink = new SingleLink();
singleLink.add(1);
singleLink.add(2);
singleLink.add(3);
System.out.println(singleLink);
}
}
测试效果
输出结果如下：
[1,2,3]
总结
通过上边的例子，我们构建了一个链表对象 并向链表对象中添加了一些元素，模拟了集合中添加元素的方法。简
单的入门就到这里了，这帮助我们去理解。另外查询节点的方法，可以通过节点图来理解即可。另外还有些链表的
操作方法，我会陆续实现。
| 
收藏
淘帖
踩
