01-链表-LinkedList-基础
2024/1/11大约 7 分钟
LinkedList-链表
什么是链表
- 链表是真正的动态数据结构
- 最简单的动态数据结构
- 更深入的理解引用(或者指针)
- 更深入的理解递归
- 辅助组成其他数据结构
链表的特点
数据存储在"节点(Node)"中
class Node {
E e;
Node next;
}- 优点: 真正的动态数据结构, 不需要处理固定容量的问题
- 缺点: 丧失了随机访问的能力
链表的ADT
- 添加元素: add();
- 根据位置索引插入元素: add(int index);
- 根据位置索引删除元素: remove(int index);
- 根据位置查询元素: get(int index);
- 根据值查询元素: get(E e);
- 根据索引位置修改元素: set(int index);
链表的基础实现
基础结构代码
public class LinkedList<E> {
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e,null);
}
public Node() {
this(null,null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head;// 记录头节点的指针
private int size; // 记录链表中的元素个数
public LinkedList(Node head, int size) {
this.head = head;
this.size = size;
}
/**
* 获取链表中的元素个数
* @return
*/
public int getSize() {
return size;
}
/**
* 返回链表是否为空
* @return boolean
*/
public boolean isEmpty() {
return size == 0;
}
}在链表头添加元素
在链表的头部添加元素, 是比较容易的，相对于数组来说,
在链表头添加元素, 需要考虑就是如何把这个元素挂接到链表的头部,
假设要把某个节点挂接到链表中, 第一步: 需要把节点的 next指向原链表的头部, 第二步: 将原链表的
head维护到当前新挂接的元素上
在上面的基础代码之上, 添加在头部添加元素的代码
/**
* 在链表头添加新元素
*/
public void addFirst (E e) {
Node node = new Node(e);
node.next = head;
head = node;
size ++;
}在链表中间添加元素
假设: 在
索引为2的地方添加元素666, 该操作经历三个步骤,- 在中间添加元素需要有个初始化时与
head节点一起的prev节点,prev游标首先遍历到索引为1的位置 - 将需要添加的元素的
next指向prev的下一个元素
- 将
prev当前所在的元素的next指针指向需要添加的这个元素
- 在中间添加元素需要有个初始化时与
关键: 找到要添加的节点的前一个节点, 所以引入了
prev的概念, 2 和 3的步骤不能颠倒, 因为如果当prev的next先指向了666, 那么666的下一个节点就不知道是谁了在原来的代码中添加以下操作代码, 注: 这是目前不太优雅的处理
/**
* 在链表的某个位置添加新元素
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add failed. Illegal index.");
}
if (index == 0) {
addFirst(e);
}else {
Node prev= head;
/**
* 找到待插入的节点的前面的节点
*/
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
size++;
}
}
/**
* 在链表的最后添加元素
* @param e
*/
public void addLast(E e) {
add(size,e);
}- 以上代码在处理头节点的添加时不够优雅, 后面有第二种实现方案, 使用虚拟节点
为链表设置虚拟的头节点
都知道: 链表头是没有头节点的, 在为链表添加头元素的过程中需要找到那个待添加的元素相应的之前的那个节点, 但是链表头是没有元素的, 此处就为链表造一个虚拟的头节点
当有了
dummyHead这个虚拟的元素之后, 在头部添加元素的时候就不需要特殊处理了
public class LinkedListDummy<E> {
private class Node {
public E e;
public Node next;
public Node(E e,Node next){
this.e = e;
this.next = next;
}
public Node (E e) {
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString() {
return e.toString();
}
}
// 虚拟头节点, 头部元素
private Node dummyHead;
private int size;
/**
* 初始化虚拟头节点的构造函数
*/
public LinkedListDummy() {
dummyHead = new Node(null,null);
size = 0;
}
/**
* 获取链表中的元素个数
*/
public int getSize() {
return size;
}
/**
* 返回链表是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在链表中间添加新元素
* 该操作不常用 练习用
*/
public void add(int index,E e){
if (index < 0 || index > size) {
throw new IllegalArgumentException("add failed. Illegal index.");
}
Node prev = dummyHead;
// 此处 prev 一直向后移动到要添加的位置
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
size++;
}
/**
* 在链表头添加新元素
*/
public void addFirst(E e) {
add(0,e);
size++;
}
/**
* 在链表末尾添加新元素
*/
public void addLast(E e) {
add(size,e);
}
}- 上面代码使用
dummyHead这个节点, 在操作指定位置添加元素的时候,prev的位置移动情况需要遍历的次数就要比上面那份不够优雅的方式少一次
遍历链表, 获取某个位置的元素
/**
* 获得链表第几个元素
* 不常用
*/
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("get failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
/**
* 获得链表第一个元素
*/
public E getFirst() {
return get(0);
}
/**
* 获得链表第一个元素
*/
public E getLast() {
return get(size - 1);
}修改链表中某个位置的元素
/**
* 修改第n个位置的元素
*/
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("update failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}查找链表中是否有元素
/**
* 查找链表中是否有元素
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {// 如果当前节点不为 null时,
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}链表中删除元素
链表删除元素的步骤
例如需要删除索引为 2 位置的元素, 首先在有虚拟头节点的链表中需要找到 索引为 2 的位置的前一个节点元素
将prev的指针指向需要删除的节点的next
再将delNode的元素的next设置为 null, 方便jvm回收
/**
* 链表中删除元素
*/
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove failed. Illegal index.");
}
Node prev = dummyHead;
// 找到要删出的位置
for (int i = 0; i < index; i++) {
prev = prev.next;// 找到待删除的节点之前的节点
}
Node delNode = prev.next; // 要删除的节点
prev.next = delNode.next;// 跨过了要删除的节点，直接指向要删除节点的下一个节点
delNode.next = null;// 把要删除的节点赋值为null
size--;
return delNode.e;
}
/**
* 删除第一个元素
* @return
*/
public E removeFirst() {
return remove(0);
}
/**
* 删除最后一个元素
* @return
*/
public E removeLast() {
return remove(size - 1);
}链表的时间复杂度分析
添加操作 O(n)
- addLast(e) O(n)
- addFirst(e) O(1)
- add(index, e) O(n/2) = O(n)
删除操作 O(n)
- removeFirst() O(1)
- removeLast() O(n)
- remove(index, e) O(n/2) = O(n)
修改操作 O(n)
- set(index, e) O(n)
查找操作
- get(index) O(n)
- contains(e) O(n)
用链表实现栈
- 先定义接口
public interface Stack<E> {
void push(E e); // 入栈
E pop();// 出栈
E peek();// 查看栈顶元素
int getSize();// 栈内的元素个数
boolean isEmpty();// 栈是否为空
}- 基于带有虚拟头节点的列表实现栈
public class LinkedListStack<E> implements Stack<E> {
private LinkedListDummy<E> list;
public LinkedListStack () {
list = new LinkedListDummy<>();
}
@Override
public void push(E e) {
list.addFirst(e);
}
@Override
public E pop() {
return list.removeFirst();
}
@Override
public E peek() {
return list.getFirst();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: top" );
res.append(list);
return res.toString();
}
}