Java数据结构-单链表的实现

Java数据结构-单链表的实现 概述 借用知乎网友的一句话：如果说 Java 是自动档轿车，C 就是手动档吉普。数据结构呢？是变速箱的工作原理。你完全可以不知道变速箱怎样工作，就把自动档的车子从 A 开到 B，而且未必就比懂得的人慢。写程序这件事，和开车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造车。但若你此生在编程领域还有点更高的追求，数据结构是绕不开的课题。 数据结构中有许多种类型，而且实现的语言也有C 也有java.今天我们来讲讲 单链表的java实现添加节点。 单链表概述 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 单链表的实现原理 说明：在单链表中，我们定义一个节点Node 包括两个部分：元数据和下一个节点的地址。节点和节点之间 通过next(即下一个节点的地址)来进行关联，这样就形成了一个链式结构。我们很轻易的就能从头（head）结点一直遍历到最后边的节点。这种结构有点像铁锁一样环环相扣。 单链表的java实现 实现数据结构的语言可以有很多，这里我们介绍使用java语言来实现。 实现添加向链表中添加节点的步骤

定义单链表对象并在内部定义一个节点对象Node 实现向单链表对象中添加节点的功能 测试

定义单链表对象 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中增加添加节点的方法 /** * 从尾部添加一个节点 * * @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 方法用于测试 // 重写方法 打印数据 @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(); } 测试 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] 总结 通过上边的例子，我们构建了一个链表对象 并向链表对象中添加了一些元素，模拟了集合中添加元素的方法。简单的入门就到这里了，这帮助我们去理解。另外查询节点的方法，可以通过节点图来理解即可。另外还有些链表的操作方法，我会陆续实现。