一. 链表的概念和分类
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
这里列出这8种链表结构
不带头单向不循环链表
不带头单向循环链表
不带头双向不循环链表
不带头双向循环链表
带头单向不循环链表
带头单向循环链表
带头双向不循环链表
带头双向循环链表
这里对于带头和不带头要注意区分一下 , 带头链表中链表的头节点是固定不变的且头节点的数值域是虚拟的 (无效的 , 不存放数据) , 不管数据在哪里插入和删除 , 头节点都不会变化 ; 而不带头链表 , 链表的第一个节点 (头节点) 是有效节点 , 数值域是有效的 , 如果在不带头链表中进行头插或者删除第一个节点 , 头节点会发生变化 .
本篇博客重点介绍下面两种链表 , 使用Java语言去实现 :
无头单向非循环链表：
结构简单，一般不会单独用来存数据 ; 实际中更多是作为其他数据结构的子结构，如 哈希桶、图的邻接表等等。
无头双向不循环链表 :
在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
二. 无头单向非循环链表实现
下图所示为无头单向非循环链表的结构
MySigleLinkedList.java
public class MySigleLinkedList { //内部类实现节点 static class ListNode { public int val;//存放元素 public ListNode next;//记录下一个节点的引用 public ListNode(int val) { this.val = val; } } public ListNode head;//记录头节点的引用 //打印链表里面的数据，默认从头开始打印 public void display() { ListNode cur = this.head; //条件不能是cur.next,否则最后一个节点无法打印 while(cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } //获取单链表的长度 public int size() { int count = 0; ListNode cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //查找某个数据key是否在单链表中 public boolean contains(int key) { ListNode cur = this.head; while(cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; } //头插法 public void addFirst(int data) { ListNode node = new ListNode(data); node.next = this.head; this.head = node; } //尾插法 public void addLast(int data) { ListNode node = new ListNode(data); ListNode cur = this.head; if(cur == null) { this.head = node; }else { //找到最后一个节点 while (cur.next != null) { cur = cur.next; } cur.next = node; } } //在任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) throws IndexWrongfulException{ if(index < 0 || index > size()) { throw new IndexWrongfulException("index位置不合法！"); } if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } //先走index-1步，找到要插入位置的前一个位置 ListNode cur = findIndexSubOne(index); ListNode node = new ListNode(data); //插入，修改指向 node.next = cur.next; cur.next = node; } private ListNode findIndexSubOne(int index) { ListNode cur = this.head; while(index-1 != 0) { cur = cur.next; index--; } return cur; } //删除第一次出现数据key的节点 public void remove(int key) { if(this.head == null) { return; } //判断头节点 if(this.head.val == key) { this.head = this.head.next; return; } //先找到key位置的上一个位置 ListNode cur = findPrevOfKey(key); if(cur == null) { System.out.println("不存在你要删除的元素"+key); return; } //删除 cur.next = cur.next.next; } private ListNode findPrevOfKey(int key) { ListNode cur = this.head; while(cur.next != null) { if(cur.next.val == key) { return cur; } cur = cur.next; } return null; } //删除所有值为key的节点 public void removeAllKey(int key) { if(this.head == null) { return; } //从第二个节点开始判断 ListNode cur = this.head.next; ListNode prev = this.head;//记录要判断节点的上一个节点 while(cur != null) { if(cur.val == key) { //删除 prev.next = cur.next; cur = cur.next; }else { prev = cur; cur = cur.next; } //最后判断头节点 if(this.head.val == key) { this.head = this.head.next; } } } /*public ListNode removeElements(int val) { if(head == null) { return null; } //从第二个元素开始判断 ListNode cur = this.head; while(cur.next != null) { if(cur.next.val == val) { cur.next = cur.next.next; }else { cur = cur.next; } } //最后判断头节点 if(this.head.val == val) { this.head = this.head.next; } return this.head; }*/ //清空单链表 public void clear() { this.head = null; } }
IndexWrongfulException.java
public class IndexWrongfulException extends RuntimeException{ public IndexWrongfulException() { } public IndexWrongfulException(String message) { super(message); } }
TestList.java
public class TestList { public static void main(String[] args) { MySigleLinkedList linkedList = new MySigleLinkedList(); System.out.println("头插测试"); linkedList.addFirst(1); linkedList.addFirst(2); linkedList.display(); System.out.println("尾插测试"); linkedList.addLast(3); linkedList.addLast(2); linkedList.addLast(1); linkedList.addLast(4); linkedList.display(); System.out.println("任意位置插入"); try { linkedList.addIndex(2,666); linkedList.addIndex(8,666); } catch(IndexWrongfulException e) { e.printStackTrace(); } linkedList.display(); System.out.println("单链表中有"+linkedList.size()+"个数据"); System.out.println("看单链表中是否包含某个数据"); System.out.println(linkedList.contains(666)); System.out.println("删除第一个指定数据"); linkedList.remove(1); linkedList.remove(9); linkedList.display(); System.out.println("删除全部的指定数据"); linkedList.removeAllKey(2); linkedList.display(); System.out.println("清空单链表后再添加一个数据"); linkedList.clear(); linkedList.addFirst(888); linkedList.display(); } }
执行结果
注意事项
在代码中需要进行遍历链表时 , 要注意区分 cur != null 和 cur.next != null 的使用 , 虽然二者都可以去遍历链表 , 但cur != null , 最后一次循环判断使cur指向为null ; 而cur.next != null 的最后一次循环判断使cur指向的是链表的最后一个节点 .
单链表中插入和删除数据 , 需要先找到要处理位置的上一个位置 , 然后再进行指针指向的修改 .
Java当中没有指针的概念 , 这里的节点通过类来实现 , 创建一个引用类型变量 , 这个引用就是Java当中的 “指针” 了 .
单链表中实现清空单链表只需要置空头节点即可 , 要与双链表中的清空区分
三. 无头双向非循环链表实现
给出结构图
MyLinkedList.java
public class MyLinkedList { //内部类定义节点 static class ListNode { public int val; public ListNode next;//记录下一个节点 public ListNode prev;//记录前一个节点 public ListNode(int val) { this.val = val; } } public ListNode head;//指向头节点 public ListNode tail;//指向尾巴节点 //打印链表 public void display() { ListNode cur = this.head; while(cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } //获取链表中元素的个数 public int size() { ListNode cur = this.head; int count = 0; while(cur != null) { count++; cur = cur.next; } return count; } //判断数据在链表中是否存在 public boolean contains(int key) { ListNode cur = this.head; while(cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; } //头插法 public void addFirst(int data) { ListNode node = new ListNode(data); if(this.head == null) { this.head = node; this.tail = node; return; } node.next = this.head; this.head.prev = node; this.head = node; } //尾插法 public void addLast(int data) { ListNode node = new ListNode(data); if(this.head == null) { this.head = node; this.tail = node; return; } this.tail.next = node; node.prev = this.tail; this.tail = node; } //在任意位置插入, 认为头节点为0位置 public void addIndex(int index, int data) { if(index < 0 || index > this.size()) { throw new IndexWrongfulException("index位置不合法"); } if(index == 0) { this.addFirst(data); return; } if(index == size()) { this.addLast(data); return; } ListNode node = new ListNode(data); ListNode cur = findIndexListNode(index); node.next = cur; node.prev = cur.prev; cur.prev.next = node; cur.prev = node; } public ListNode findIndexListNode(int index) { ListNode cur = this.head; while(index != 0) { cur = cur.next; index--; } return cur; } //删除第一个出现的指定元素 public void remove(int key) { ListNode cur = this.head; while(cur != null) { if(cur.val == key) { //如果要删除的是头节点 if(this.head == cur) { this.head = this.head.next; //如果链表中只有一个节点 if(this.head != null){ this.head.prev = null; } }else{ cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else {//如果要删除的是尾巴节点 this.tail = cur.prev; } } return; } cur = cur.next; } } //删除全部的指定元素 public void removeAll(int key) { ListNode cur = this.head; while(cur != null) { if(cur.val == key) { //如果要删除的是头节点 if(this.head == cur) { this.head = this.head.next; //如果链表中只有一个节点 if(this.head != null){ this.head.prev = null; } }else{ cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else {//如果要删除的是尾巴节点 this.tail = cur.prev; } } } cur = cur.next; } } //清空 public void clear() { ListNode cur =this.head; while(cur != null) { cur.prev = null; cur.next = null; cur = cur.next; } this.head = null; this.tail = null; } }
IndexWrongfulException.java
public class IndexWrongfulException extends RuntimeException{ public IndexWrongfulException() { } public IndexWrongfulException(String message) { super(message); } }
TestList.java
public class TestList { public static void main(String[] args) { MyLinkedList list = new MyLinkedList(); System.out.println("头插测试"); list.addFirst(1); list.addFirst(2); list.addFirst(3); list.display(); System.out.println("尾插测试"); list.addLast(4); list.addLast(5); list.addLast(6); list.display(); System.out.println("获取链表中元素的个数"); System.out.println(list.size()); System.out.println("判断数据在链表中是否存在"); System.out.println(list.contains(4)); System.out.println(list.contains(8)); System.out.println("在任意位置插入"); list.addIndex(0, 666); list.addIndex(3, 666); list.addIndex(list.size(), 666); list.display(); System.out.println("删除第一个出现的指定元素"); list.remove(4); list.display(); System.out.println("删除全部的指定元素"); list.removeAll(666); list.display(); System.out.println("清空链表后再添加一个元素"); list.clear(); list.addFirst(888); list.display(); } }
执行结果
注意事项
与单链表中的插入和删除实现进行区分 , 这里双链表中的插入和删除 , 因为此时链表是双向的 , 所以不需要像单链表一样找要处理位置的前一个位置 , 只需要找到要处理的位置去改变前驱和后记指针指向即可 .
在进行删除元素操作时 , 需要考虑的细节比较多 , 特别需要注意删除头节点与尾节点时的操作(考虑prev为null和next为null , 与删除中间节点不同) , 具体实现看上面给出的代码 .
注意双链表的清空链表实现 , 与单链表中的进行区分 , 双链表中需要手动去将每个节点的两个指针域置为null , 最后再将head和tail去置空 .
