前面我们所学习的线性数据结构
1、动态数组
2、栈
3、队列
它们的底层都是依托于静态的数组所实现：靠resize解决固定容量的问题
一、链表
1、链表：真正的动态数据结构
优点：不需要处理固定容量的问题，是真正的动态数据结构
缺点：丧失了随机访问的能力
2、创建Node
class Node<T> {
T data; //结点本身的数据
Node next; // 指向下个结点
public Node(T data) {
this.data = data;
this.next = null;
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}3、对链表进行增加操作
<1>链表头添加元素
<2>在链表中间添加元素
关键点：找到要待添加位置的前一个结点
<3> 在链表的尾部添加元素
4、使用虚拟头结点（解决在头部添加结点的特殊处理）
注意： 添加完成后，需要更新头节点
5、链表的属性和方法
//链表相关的属性和方法
private Node head; //链表的头
private int size; //表示链表中有多少个结点
public SelfLinkedList() {
//创建一个虚拟头结点
Node dummyHead = new Node(Integer.MIN_VALUE);
this.head = dummyHead;
this.size = 0;
}
//判断链表是否为空
public boolean isEmpty() {
return this.size == 0;
}
//向链表中添加结点
//在头部添加
public void addHead(T data) {
add(0, data);
}
//在尾部添加
public void addTail(T data) {
add(this.size, data);
}
/* public void add(int index,T data){
//判断index 位置是否有效
if (index < 0 || index > this.size){
throw new IllegalArgumentException("index is invaild");
}
//1、创建一个结点
Node node = new Node(data);
//特殊处理1，如果索引为0
if (index == 0){
this.head = new Node(data,this.head);
this.size++;
return;
}
//2、找前驱结点
Node pre = this.head;
for (int i = 1; i < index; i++) {
pre = pre.next;
}
//3、开始进行结点的连接
node.next = pre.next;
pre.next = node;
this.size++;
}*/
//在任意位置添加
public void add(int index, T data) {
//判断index 位置是否有效
if (index < 0 || index > this.size) {
throw new IllegalArgumentException("index is invaild");
}
//1、创建一个结点
Node node = new Node(data);
//2、找前驱结点
Node pre = this.head;
for (int i = 1; i <= index; i++) {
pre = pre.next;
}
//3、开始进行结点的连接
node.next = pre.next;
pre.next = node;
this.size++;
}
//重写toString , 打印整个链表中的元素
@Override
public String toString() {
//从this.head 开始一直向后找
Node curNode = this.head.next;
StringBuilder sb = new StringBuilder();
while (curNode != null) {
sb.append(curNode.data + "--->");
curNode = curNode.next;
}
sb.append("null");
return sb.toString();
}
//从链表中查找指定的元素是否存在
public boolean contains(T data) {
//遍历链表时，头结点不能动
Node curNode = this.head.next;
while (curNode != null) {
if (curNode.data.equals(data)) {
return true;
}
curNode = curNode.next;
}
return false;
}
//获取链表中元素的个数
public int getSize() {
return this.size;
}
//获取链表的头结点
public Optional getFirst() {
if (this.head.next == null) {
return Optional.empty();
}
return Optional.ofNullable(this.head.next.data);
}
//获取链表的尾结点
public Optional<T> getLast() {
if (this.head.next == null) {
return Optional.empty();
}
//遍历链表时，头结点不能动
Node<T> curNode = this.head;
while (curNode.next != null) {
curNode = curNode.next;
}
return Optional.of(curNode.data);
}
//从链表中获取任意位置的头结点
public T get(int index) {
if (index < 0 || index >= this.size) {
throw new IllegalArgumentException("index is invalid");
}
Node<T> curNode = this.head.next;
int i = 0;
while (i < index) {
curNode = curNode.next;
i++;
}
return curNode.data;
}
// 从链表的头部删除元素
public T removeHead() {
if (this.isEmpty()) {
return null;
}
Node<T> delNode = this.head.next;
this.head.next = delNode.next;
delNode.next = null;
//更新size
this.size--;
return delNode.data;
}
// 从链表的尾部去删除元素
public T removeTail() {
if (this.isEmpty()) {
return null;
}
Node<T> pre = this.head;
while (pre.next.next != null) {
pre = pre.next;
}
Node<T> delNode = pre.next;
pre.next = delNode.next;
delNode.next = null;
//更新size
this.size--;
return delNode.data;
}
public void remove2(T val){
//更新头结点
this.head.next = recusionRemove(this.head.next,val);
}
// 使用递归的方式从链表中删除元素
// 递归函数的语义，从以node为头结点的链表中删除元素value，返回值为删除之后链表的头结点
private Node recusionRemove(Node node, T value) {
//递归终止的条件
if (node == null) {
return null;
}
//递归操作
if (node.data.equals(value)) {
this.size--;
return node.next;
} else {
node.next = recusionRemove(node.next, value);
return node;
}
}
// 删除任意位置的结点
public T remove(int index) {
if (index < 0 || index >= this.size) {
throw new IllegalArgumentException("index is invalid");
}
//找删除结点的前驱
Node<T> pre = this.head;
int i = 0;
while (i < index) {
pre = pre.next;
i++;
}
Node<T> delNode = pre.next;
pre.next = delNode.next;
delNode.next = null;
this.size--;
return delNode.data;
}
//根据值从链表中删除元素(使用虚拟头结点)
public int removeByValue(T val) {
int count = 0;
// 定义前驱结点
Node<T> pre = this.head;
while (pre.next != null) {
Node<T> curNode = pre.next;
if (curNode.data.equals(val)) {
pre.next = pre.next.next;
curNode.next = null;
this.size--;
count++;
} else {
pre = pre.next;
}
}
return count;
}
//根据值从链表中删除元素(不使用虚拟头结点)
public int removeByValue2(T val) {
int count = 0;
Node<T> realHead = this.head.next;
while (realHead != null && realHead.data.equals(val)) {
realHead = realHead.next;
this.size--;
count++;
}
//判断链表是否为空
if (realHead == null) {
return count;
}
//假设头结点不是要删除的结点
Node pre = realHead;
while (pre.next != null) {
Node<T> delNode = pre.next;
if (delNode.data.equals(val)) {
pre.next = delNode.next;
delNode.next = null;
this.size--;
count++;
} else {
pre = pre.next;
}
}
return count;
}6、从链表中删除元素
7、链表的时间复杂度分析
八、使用链表实现栈
以链表作为栈的底层数据结构。
public class LinkedStack<T> implements Stack_I<T> {
private SelfLinkedList<T> data;
public LinkedStack(){
this.data = new SelfLinkedList<>();
}
@Override
public void push(T ele) {
this.data.addHead(ele);
}
@Override
public T pop() {
try {
return this.data.removeHead();
} catch (Exception e) {
return null;
}
}
@Override
public T peek() {
return this.data.getFirst().orElse(null);
}
@Override
public boolean isEmpty() {
return this.data.isEmpty();
}
@Override
public int getSize() {
return this.data.getSize();
}
}
