数据结构-链表

概念

链表 [Linked List]：链表是由一组不必相连【不必相连：可以连续也可以不连续】的内存结构 【节点】，按特定的顺序链接在一起的抽象数据类型。

分类:

单向链表双向链表循环链表

单项链表

链表是有序列表，在内存中的存储实行如下图：

链表的结构特点

链表是以节点的方式来存储的每个节点都包含了data域(存放数据)，next域指向下一个节点链表的存储空间不是连续的链表分为有头节点的和没有头节点的

java代码实现单向链表

先定义链表节点类 /** * 链表的节点 */ class LinkedNode { // 数据节点 private int dataNode; // 下一个节点 private LinkedNode next; /** * 构造函数 * * @param dataNode 数据元素 */ public LinkedNode(int dataNode) { this.dataNode = dataNode; } } 定义链表类 /** * 定义单链表类 * 管理链表的每一个节点 */ class SingleLinkedList { // 初始化头节点 LinkedNode head = new LinkedNode(0); /** * 添加节点到单项链表 * 1、找到链表的最后一个节点 * 2、把最后节点的next指向新的节点 * 没有排序的都是添加到最后 */ void add(LinkedNode linkedNode) { // 创建一个临时节点执行头节点，头节点不能动，动的话会打乱链表结构 LinkedNode temp = head; // 1、找到链表的最后位置 // 循环遍历找到最后位置 for (; true ; ) { if (temp.next == null) { break; } // 没有找到最后，temp后移 temp = temp.next; } // 循环退出说明temp已经是最后一个节点 // 把最后一个节点的next指向新的元素 temp.next = linkedNode; } /** * 遍历显示链表 */ void showLinkedList() { if (this.head.next == null) { System.out.println("链表数据为空"); return; } // 通过辅助变量来遍历链表 LinkedNode temp = this.head.next; // 循环遍历链表 while (true) { if (temp == null) { break; } // 输出节点 System.out.println(temp.dataNode); // next 后移 temp = temp.next; } } }