一、链表
1. 了解指针/ 引用：
先看这一段代码：
class Home {
private String address;
public Home(String address) {
this.address = address;
}
@Override
public String toString() {
return "Home{" +
"address='" + address + '\'' +
'}';
}
}
class Person {
private String name;
private int age;
private Home home;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public void setHome(Home home) {
this.home = home;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
", home=" + home +
'}';
}
}
public class ReferenceTest {
public static void main(String[] args) {
Person person = new Person("jeffy", 12);
person.setHome(new Home("杭州"));
System.out.println(person);
}
}
内存中分布：
内存中分布.png
2. (O_O)? 为什么需要链表？
能不能设计一种数据结构，可以合理的充分的利用非连续的内存空间？
链表 (#.#)
链表也是一个线性表结构，链表不需要连续的内存空间，所以链表可以充分的利用内存空间！
3. 链表VS数组：
链表是动态数据结构，链表天然的支持动态扩容，数组需要进行resize才可以扩容。
链表可以充分的利用非连续的内存空间，提高内存利用率。
在存储相同数量的数据时，链表需要的内存空间比数组大。
二、单向链表
1. 链表的基本实现
package com.douma.line;
public class Linkedlist<E> {
// 作为私有类
private class Node {
E e;
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);
}
// 打印Node可调用 toString方法
@Override
public String toString() {
return e.toString();
}
}
// 链表还需什么属性？
// 虚拟头结点
private Node dummyHead;
// 长度
private int size;
// 该链表 的构造方法 无参构造
public Linkedlist() {
dummyHead = new Node();
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
2. 链表查询指定索引的元素
// 可以写成：
Node curr = head; // head 指向索引为 0 的节点
curr = curr.next; // curr 的索引为 1
curr = curr.next; // curr 的索引为 2
curr = curr.next; // curr 的索引为 3
// 上述代码也可以写成：
for (int i = 0; i < 3; i++) {
curr = curr.next;
}
- 注意：索引和size的关系。 size = 最大索引值 + 1。size指向null。
3. 关于链表的基本操作
查询：
/**
* 查询指定索引的节点的值
* @param index
* @return
*/
// 时间复杂度： O(n)
public E get(int index) {
// 检查 index 的合法性
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed, index must >= 0 and < size");
Node curr = dummyHead.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.e;
}
// 时间复杂度： O(1)
public E getFirst() {
return get(0);
}
// 时间复杂度： O(n)
public E getLast() {
return get(size - 1);
}
修改：
/**
* 修改指定索引的节点元素: 修改索引为3的节点的值为88
* @param index :3
* @param e 88
*/
// 时间复杂度： O(n)
public void set(int index, E e) {
// 检查 index 的合法性
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed, index must >= 0 and < size");
Node curr = dummyHead.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
} // 此时curr在索引为3的地方
curr.e = e;
}
新增：
/**
* 在链表表头新增节点
* @param e 新增节点需要存储的数据
*/
// 时间复杂度： O(1)
public void addFirst(E e) {
add(0, e);
}
// 也可以这样写
public void addFirst2(E e) {
Node newNode = new Node(e);
newNode.next = head;
head = newNode;
size++;
}
// 时间复杂度： O(n)
public void addLast(E e) {
add(size, e);
}
/**
* 在指定索引的位置插入新的节点
* @param index 需要插入的位置
* @param e 需要插入的数据
*/
// 时间复杂度： O(n)
public void add(int index, E e) {
// 检查 index 的合法性
if (index < 0 || index > size)
throw new IllegalArgumentException("add failed, index must >= 0 and <= size");
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
prev.next = new Node(e, prev.next);
size++;
}
- 在链表中间添加节点：例如，将节点22 插入到第二个节点的后面；即：将22插入到索引为2的位置上。
- 先需要找到，索引2的前一个节点 prev。从链表头开始往后找。
- node.next = prev.next;
- prev.next = node;
注意：后面的两步是不能交换的！
删除：
删除头结点：
- Node delNode = head；
- head = head.next;
- delNode.next = null;
删除中间的节点：删除索引为3的节点
- 从链表头，遍历三次，找到待删除节点的前一个节点prev。
- 临时存储待删除的节点 Node delNode = prev.next。
- prev.next = delNode.next。
- delNode.next = null。
/**
* 删除链表的头节点
* @return
*/
// 时间复杂度： O(1)
public E removeFirst() {
return remove(0);
}
// 时间复杂度： O(n)
public E removeLast() {
return remove(size - 1);
}
/**
* 删除指定索引的节点，并返回删除的节点的值
* @param index
* @return
*/
// 时间复杂度： O(n)
public E remove(int index) {
// 检查 index 的合法性
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove failed, index must >= 0 and < size");
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.e;
}
public void removeElement(E e) {
if (dummyHead.next == null)
throw new IllegalArgumentException("removeElement failed, LinkedList is Empty");
Node prev = dummyHead;
Node curr = dummyHead.next;
while (curr != null) {
if (curr.e.equals(e)) {
break;
}
prev = curr;
curr = curr.next;
}
prev.next = curr.next;
curr.next = null;
}
4. 哨兵节点(虚拟节点)
在链表的表头添加一个节点dummyHead
虚拟节点.png
5. 链表遍历
链表中是否包含指定值 109
for (int i = 0; i< size; i++) {
if (curr.e == 109) {
return true
}
curr = curr.next;
}
可以使用while循环来代替for循环：
while (curr != null) {
if (curr.e == 109) {
return true
}
curr = curr.next;
}
/**
* 判断链表中是否存在指定元素
* @param e
* @return
*/
// 时间复杂度： O(n)
public boolean contains(E e) {
Node curr = dummyHead.next;
while (curr != null) {
if (curr.e.equals(e)) {
return true;
}
curr = curr.next;
}
return false;
}
6. 重写toString方法
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node curr = dummyHead.next;
while (curr != null) {
sb.append(curr + "=>");
curr = curr.next;
}
sb.append("null");
return sb.toString();
}
