基础数据结构------单链表

1、链表使用的解决方案

【链表的概述】

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

【链表的分类】

链表有很多种不同的类型：单向链表，双向链表以及循环链表。 

由于N 个结点依次相链构成的链表的每个结点中只包含一个指针域，故又称单链表或线性链表。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

2、带头节点单向链表

定义头节点

private Node head = null;   // 头节点

 节点类

private static class Node {int value;   // 节点的值Node next;   // 下一个节点public Node(int value, Node next) {this.value = value;this.next = next;}}

为什么节点类用 private 修饰？

链表和节点之间存在整体和部分的关系，对外隐藏节点的属性和实现细节。链表类封装了节点类的属性。

为什么节点类用 static 关键字修饰？

static 可以在内部类变量和外部的成员变量没有关系时添加。

【采用头插法创建链表】

public void addFirst(int value) {// 链表无节点//head = new Node(value, null);// 链表有节点head = new Node(value, head);}

【遍历链表】

public void loop1 (Consumer<Integer> consumer) {Node p = head;while (p != null) {  //p当前节点为空时结束循环consumer.accept(p.value);p = p.next;     //节点位置后移}}

list.loop1(value -> System.out.println(value));//输出: 4 3 2 1

public void loop2(Consumer<Integer> consumer) {for (Node p = head; p != null; p = p.next) {consumer.accept(p.value);}}

list.loop2(value -> System.out.println(value));//输出: 4 3 2 1

@Overridepublic Iterator<Integer> iterator() {// 匿名内部类 ----> 带名字内部类return new NodeIterator();}private class NodeIterator implements Iterator<Integer> {Node p = head;  // 新节点指向头节点@Overridepublic boolean hasNext() { //判断有无下一个节点return p != null;}@Overridepublic Integer next() {  // 当前节点的值和指向下一个节点的地址int value = p.value;p = p.next;return value;}}

 【采用尾插法创建链表】

// 查找最后一个节点private Node findLast() {//判断是否为空链表if (head == null){return null;}Node p;for (p = head; p.next != null; p = p.next) {}return p;}// 尾插法public void addLast(int value) {// 找到最后一个节点Node last = findLast();//空链表if (last == null){addFirst(value);return;}// 新节点last.next = new Node(value, null);}

【获取节点的索引】

public void getIndex () {int i = 0;for (Node p = head; p != null; p = p.next, i++) {System.out.println(p.value + "索引是:" + i);}}

【根据指定的索引获取对应节点】 

public int get (int index) {Node node = findNode(index);if (node == null) {// 抛出异常throw IllegalIndex(index);}return node.value;}

// 参数不合法异常private IllegalArgumentException IllegalIndex(int index) {return new IllegalArgumentException(String.format("index[%d] " + index + "不合法 %n"));}

【向指定索引位置插入节点】

public void insert(int index, int value) {//索引为0if (index == 0) {addFirst(value);return;}// 找到上一个节点Node prev = findNode(index - 1);//找不到节点if (prev == null) {throw IllegalIndex(index);}// 新节点在上一个节点之后prev.next = new Node(value, prev.next);}

【删除节点】

// 删除第一节点public void removeFirst() {if (head == null) {throw IllegalIndex(0);}head = head.next;}// 删除指定索引的节点public void remove(int index) {// 索引为 0if (index == 0) {removeFirst();return;}Node prev = findNode(index - 1);if (prev == null) {throw IllegalIndex(index);}// 待删除的节点Node removed = prev.next;// 删除节点 是nullif (removed == null) {throw IllegalIndex(index);}prev.next = removed.next;}

3、哨兵的单向链表

当链表为空时，执行addLast(int value)、insert(int index, int value)、remove(int index)和链表非空时，执行addLast(int value)、insert(int index, int value)、remove(int index)的逻辑不同。采用哨兵节点为了简化addLast(int value)、insert(int index, int value)、remove(int index)操作链表。

【哨兵节点】

private Node head = new Node(100, null);

【初始化节点对象】

private static class Node {int value;   // 节点的值Node next;   // 下一个节点public Node(int value, Node next) {this.value = value;this.next = next;}}

【链表的遍历】

// 遍历链表1: while  consumer 要执行的操作public void loop1(Consumer<Integer> consumer) {Node p = head.next;while (p != null) {  //p当前节点为空时结束循环consumer.accept(p.value);p = p.next;     //节点位置后移}}//遍历链表2: fori形式 consumer 要执行的操作public void loop2(Consumer<Integer> consumer) {for (Node p = head.next; p != null; p = p.next) {consumer.accept(p.value);}}//遍历3：迭代器@Overridepublic Iterator<Integer> iterator() {// 匿名内部类 ----> 带名字内部类return new NodeIterator();}private class NodeIterator implements Iterator<Integer> {Node p = head.next;  // 新节点指向头节点@Overridepublic boolean hasNext() { //判断有无下一个节点return p != null;}@Overridepublic Integer next() {  // 当前节点的值和指向下一个节点的地址int value = p.value;p = p.next;return value;}}

【查找最后一个节点】

private Node findLast() {Node p;for (p = head; p.next != null; p = p.next) {}return p;}

【根据索引查找指定的节点】

private Node findNode(int index) {int i = -1;for (Node p = head; p != null; p = p.next, i++) {if (i == index) {return p;}}return null;}

【从尾部插入节点】

public void addLast(int value) {// 找到最后一个节点Node last = findLast();// 新节点last.next = new Node(value, null);}

【获取索引指定的节点】

public int get(int index) {Node node = findNode(index);if (node == null) {// 抛出异常throw IllegalIndex(index);}return node.value;}

【获取链表的节点索引】

public void getIndex() {int i = 0;for (Node p = head.next; p != null; p = p.next, i++) {System.out.println(p.value + "索引是:" + i);}}

【向指定位置插入节点】

public void insert(int index, int value) {// 找到上一个节点Node prev = findNode(index - 1);//找不到节点if (prev == null) {throw IllegalIndex(index);}// 新节点在上一个节点之后prev.next = new Node(value, prev.next);}

【参数不合法异常】

private IllegalArgumentException IllegalIndex(int index) {return new IllegalArgumentException(String.format("index[%d] 不合法 %n" ));}

【删除节点】

public void remove(int index) {Node prev = findNode(index - 1);if (prev == null) {throw IllegalIndex(index);}// 待删除的节点Node removed = prev.next;// 删除节点 是nullif (removed == null) {throw IllegalIndex(index);}prev.next = removed.next;}// 删除第一节点public void removeFirst() {remove(0);}