链表
文章目录
顺序表的缺陷
上篇文章我们介绍了顺序表,顺序表的底层是数组，当我们在进行数组的添加和删除时，需要将后序元素依次移动位置，使得时间复杂度为O(N),效率比较低。因此:java引进了LinkedList，即链表结构。
概念
链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。简单来说，链表不会按照顺序表的存储结构去存储数据，而是在每一个节点里存放下个节点的地址 。
结构
这是一个简单的单向链表的结点，val表示的是当前结点要存的值，next表示引用，用来存放下一个结点的地址。
由于Java中不存在指针，所以每一个结点通常为一个类，而next是一个结点类实例的引用
创建链表
我们介绍了链表，可是该如何创建一个链表呢？
在Java中我们用类来表示链表的结构
public static class Node { int value;//值 Node next;//结点引用，引用当前节点的下一节点 public Node(int value) { this.value = value; } }
结点的插入
在链表中插入一个节点时，一般有3种方法：头插、尾插、指定位置插入
头插
在链表的起始位置插入结点。
public void addFirst(int data) { Node node = new Node(data); node.next = head; head = node; }
代码很简单，思路也很简单
尾插
与头插相似，只是在最后一个结点的位置插入新结点。
//尾插法 public void addLast(int data) { //创建新链表 Node node = new Node(data); //判断链表是否为空 if (head == null) { addFirst(data); return; } //后面节点 Node current = head; while (current.next != null) { current = current.next; } current.next = node; }
指定位置插入
private void checkRange(int index) { if (index < 0 || index > size()) { throw new IndexOutOfBoundsException("下标非法 i=" + index); } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) { //检查index合法性 checkRange(index); //首位 if (index == 0) { addFirst(data); return; } //尾部 if (index == size()) { addLast(data); return; } //中间位置 //首先找到所找节点的上一节点 Node preNode = findPreNode(index); //创建新节点 Node node = new Node(data); //用node.next引用preNode.next node.next = preNode.next; //preNode.next引用新节点 preNode.next = node; } private Node findPreNode(int index) { //创建临时节点 Node current = head; for (int i = 0; i < (index - 1); i++) { current = current.next; } return current; }
查找是否包含关键字key是否在单链表当中
遍历数组即可
public boolean contains(int key) { //遍历链表 Node current = head; while (current != null) { if (current.value == key) { return true; } current = current.next; } return false;
删除元素
这个会出现2种情况：删除第一次出现的关键字key和删除出现的所有关键字key
删除第一次出现的关键字key
public void remove(int key) { //若为头节点 if (head.value == key) { head = head.next; return; } //不是头节点 Node current = head; while (current != null) { if (current.next.value == key) { current.next = current.next.next; return; } current = current.next; } }
删除出现的所有关键字key
public void removeAllKey(int key) { //判断链表是否为空 if (head == null) { return; } //出现在首位 if (head.value == key) { head = head.next; } //不为空 //两个临时变量 Node current = head.next; Node prev = head; while (current != null) { if (current.value == key) { prev.next = current.next; } else { prev = current; } current = current.next; } }
获取链表长度
public int size() { //遍历每个节点，统计节点个数 Node current = head; int count = 0; while (current != null) { count++; current = current.next; } return count; }
清空链表
public void clear() { //手动将每个节点置空 Node current = head; while (current != null) { //得到下一个节点 Node nextNode = current.next; current.next = null; current = nextNode; } //最简便方法 head = null; }
链表打印
public void display() { //创建一个临时变量引用head Node current = head; StringBuilder sb = new StringBuilder(); sb.append("["); while (current != null) { sb.append(current.value); //最后一个节点不加空格 if (current.next != null) { sb.append(" "); } current = current.next; } sb.append("]"); System.out.println(sb.toString()); }
以上就是链表的基本操作了，下面是全部源码
import java.util.Stack; public class SingleLinkedList { public static class Node { int value; Node next; public Node(int value) { this.value = value; } } public Node head; //头插法 public void addFirst(int data) { Node node = new Node(data); node.next = head; head = node; } //尾插法 public void addLast(int data) { //创建新链表 Node node = new Node(data); //判断链表是否为空 if (head == null) { addFirst(data); return; } //后面节点 Node current = head; while (current.next != null) { current = current.next; } current.next = node; } private void checkRange(int index) { if (index < 0 || index > size()) { throw new IndexOutOfBoundsException("下标非法 i=" + index); } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) { //检查index合法性 checkRange(index); //首位 if (index == 0) { addFirst(data); return; } //尾部 if (index == size()) { addLast(data); return; } //中间位置 //首先找到所找节点的上一节点 Node preNode = findPreNode(index); //创建新节点 Node node = new Node(data); //用node.next引用preNode.next node.next = preNode.next; //preNode.next引用新节点 preNode.next = node; } private Node findPreNode(int index) { //创建临时节点 Node current = head; for (int i = 0; i < (index - 1); i++) { current = current.next; } return current; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { //遍历链表 Node current = head; while (current != null) { if (current.value == key) { return true; } current = current.next; } return false; } //删除第一次出现关键字为key的节点 public void remove(int key) { //若为头节点 if (head.value == key) { head = head.next; return; } //不是头节点 Node current = head; while (current != null) { if (current.next.value == key) { current.next = current.next.next; return; } current = current.next; } } //删除所有值为key的节点 public void removeAllKey(int key) { //判断链表是否为空 if (head == null) { return; } //出现在首位 if (head.value == key) { head = head.next; } //不为空 //两个临时变量 Node current = head.next; Node prev = head; while (current != null) { if (current.value == key) { prev.next = current.next; } else { prev = current; } current = current.next; } } //得到单链表的长度 public int size() { //遍历每个节点，统计节点个数 Node current = head; int count = 0; while (current != null) { count++; current = current.next; } return count; } public void clear() { //手动将每个节点置空 Node current = head; while (current != null) { //得到下一个节点 Node nextNode = current.next; current.next = null; current = nextNode; } //最简便方法 head = null; } public void display() { //创建一个临时变量引用head Node current = head; StringBuilder sb = new StringBuilder(); sb.append("["); while (current != null) { sb.append(current.value); //最后一个节点不加空格 if (current.next != null) { sb.append(" "); } current = current.next; } sb.append("]"); System.out.println(sb.toString()); /*while(current!=null){ System.out.print(current.value+" "); current=current.next; } System.out.println();*/ } public void printList() { if (head == null) { System.out.println(""); return; } Stack<Node> stack = new Stack<>(); Node current = head; while (current != null){ stack.push(current); current=current.next; } while(!stack.empty()){ System.out.print(stack.pop().value+" "); } System.out.println(); } }
