Java实现单链表

• 一、一链表的概念及结构
• 二、头节点与头指针的异同
• 三、代码实现

一、一链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

注意：

• 从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
• 现实中结点一般是从堆上申请出来的。
• 从堆上申请出来的空间，是按照一定策略来分配的，两次申请可能是连续，也可能是不连续的

二、头节点与头指针的异同

• 头指针
  1.头指针是指链表指向第一个结点的指针，若链表有头节点，则是指向头节点的指针。
  2.头指针是具有标识作用，所以常用头指针冠以链表的命名
  3.无论链表是否为空，头指针均不为空。头指针是链表的必要元素
  若头指针为空，则链表不存在。
• 头节点
  1.头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
  2.有了头结点，对在第一元素结点前插入结点和删除第一节点，其操作与其他结点的操作就统一了
  3.头节点不一定是链表的必须元素

三、代码实现

里面包含常用的一些操作：
1.头插法
2.尾插法
3.遍历
4.元素的删除

public class LinkedList {//创建结点类，结点脱离类一般无意义，所以设定为静态类static class Node {//数据域int val;//引用后继指针地址Node next;public Node(int val) {this.val = val;}}//定义头节点Node head;public void addFirst(int val) {Node node = new Node(val);if (head == null) {head = node;return ;}node.next = head;head = node;}//尾插法public void addLast(int val) {Node node = new Node(val);if (head == null) {head = node;return ;}//此时要定义一个临时头节点，以便我们找到链表的尾部//并且我们是不希望改动链表的头节点，所以临时结点很重要Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = node;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int val) {if (head == null) {return false;}//判断所给的索引合法性if (index < 0 || index > size()) {throw new RuntimeException("the index is not illegal!");}//第一个位置插入的时候，此时就是头插法if (index == 0) {addFirst(val);return true;}//最后一个位置插入则为尾插法if (index == size()) {addLast(val);return true;}//最后考虑中间位置的插入即可//1.定义临时头结点，先走到待插入位置的前一个位置Node temp = head;while (index > 1) {temp = temp.next;index--;}//2.对元素进行插入Node node = new Node(val);node.next = temp.next;temp.next = node;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {if (head == null) {return false;}//只要在链表找到我们就返回false就行Node temp = head;while (temp != null) {if (temp.val == key) {return true;}temp = temp.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key) {if (head == null) {return ;}//只要存在我们才可以去删除if (!contains(key)) {throw new RuntimeException("the key is not exist !");}//如果是头节点的情况就直接删除if (head.val == key) {head  = head.next;return ;}//1.找到第一次出现的关键字key的前一个位置Node temp = head;while (temp != null && temp.next != null) {if (temp.next.val == key) {temp.next = temp.next.next;return;}temp = temp.next;}}//删除所有值为key的节点public void removeAllKey(int key) {if (head == null) {return ;}while (contains(key)) {remove(key);}}//得到单链表的长度public int size() {if (head == null) {return 0;}Node temp = head;int size = 0;while (temp != null) {size++;temp = temp.next;}return size;}public void display() {//遍历链表，这个是一定要掌握的,也不难if (head == null) {return ;}Node temp = head;while (temp != null) {System.out.print(temp.val + " ");temp = temp.next;}}//清空链表public void clear() {//这个我们枪打出头鸟就行head =null;}}