数据结构与算法：链表
链表（Linked List）
- 动态数组有个明显的缺点
- 可能会造成内存空间的大量浪费
- 链表可以办到用到多少就申请多少内存
- 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
链表的设计
链表的方法都和动态数组的方法一致，所以两者通过继承AbstractList，重写方法实现各自的功能。
清空元素
指定索引位置添加元素
删除元素
虚拟头节点
有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）。因为在边界(index=0)，这个位置的一些操作是要格外的注意，增加了虚拟头节点之后，这些操作便可以统一处理。
代码实现：单向链表
顶层接口：
public interface MyList<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清楚所有元素
*/
void clear();
/**
* 列表元数数量
*
* @return 数量
*/
int size();
/**
* 判断列表是否为空
*
* @return 是否为空
*/
boolean isEmpty();
/**
* 是否包含某个元素
*
* @param element 元素
* @return 返回
*/
boolean contains(E element);
/**
* 添加元素到尾部
*
* @param element 元素
*/
void add(E element);
/**
* 获取index位置的元素
*
* @param index 索引位置
* @return 返回元素
*/
E get(int index);
/**
* 设置index位置的元素
*
* @param index 索引位置
* @param element 元素
* @return 原来的元素ֵ
*/
E set(int index, E element);
/**
* 在index位置插入一个元素
*
* @param index 索引
* @param element 元素
*/
void add(int index, E element);
/**
* 删除index位置的元素
*
* @param index 索引
* @return 元素
*/
E remove(int index);
/**
* 查看元素的索引
*
* @param element 元素
* @return 索引
*/
int indexOf(E element);
}
抽象父类：
public abstract class MyAbstractList<E> implements MyList<E> {
protected int size;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
@Override
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
单向链表实现：
public class SingleLinkedList<E> extends MyAbstractList<E> {
//虚拟头节点
private Node<E> first;
public SingleLinkedList() {
first = new Node<>(null, null);
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
Node<E> prev = index == 0 ? first : node(index - 1);
prev.next = new Node<>(element, prev.next);
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> prev = index == 0 ? first : node(index - 1);
Node<E> node = prev.next;
prev.next = node.next;
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 获取index位置对应的节点对象
*
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first.next;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
}
单向循环链表
单向循环链表就是单项链表的尾元素的next指向头元素
代码实现
package com.msr.datastructure.linklist;
/**
* @description: 虚拟头节点：单项循环链表
* @author: MaiShuRen
* @date: 2020/5/24 11:12
* @version: v1.0
*/
public class SingleCircleLinkedList<E> extends MyAbstractList<E> {
private Node<E> first;
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(element).append("_").append(next.element);
return sb.toString();
}
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) {
Node<E> newFirst = new Node<>(element, first);
// 拿到最后一个节点
Node<E> last = (size == 0) ? newFirst : node(size - 1);
last.next = newFirst;
first = newFirst;
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
Node<E> last = node(size - 1);
first = first.next;
last.next = first;
}
} else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) {
return i;
}
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}
双向链表
代码实现
public class MyLinkedList<E> extends MyAbstractList<E> {
private Node<E> first;
private Node<E> last;
@Override
public void clear() {
size = 0;
first = null;
last = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
// size == 0
// index == 0
// 往最后面添加元素
if (index == size) {
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
// 这是链表添加的第一个元素
if (oldLast == null) {
first = last;
} else {
oldLast.next = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
// index == 0
if (prev == null) {
first = node;
} else {
prev.next = node;
}
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
// index == 0，第一个元素
if (prev == null) {
first = next;
} else {
prev.next = next;
}
// index == size - 1，最后一个元素
if (next == null) {
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
Node<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null) {
return i;
}
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) {
return i;
}
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 获取index位置对应的节点对象
*
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
//1.如果index小于链表容量的一半，则从首元素开始向后查找
if (index < (size >> 1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
//2.index大于链表容量的一半，从尾元素向前查找
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.element);
} else {
sb.append("null");
}
sb.append("_").append(element).append("_");
if (next != null) {
sb.append(next.element);
} else {
sb.append("null");
}
return sb.toString();
}
}
}
双向循环链表
代码实现
public class CircleLinkedList<E> extends MyAbstractList<E> {
private Node<E> first;
private Node<E> last;
private Node<E> current;
public void reset() {
current = first;
}
public E next() {
if (current == null) {
return null;
}
current = current.next;
return current.element;
}
public E remove() {
if (current == null) return null;
Node<E> next = current.next;
E element = remove(current);
if (size == 0) {
current = null;
} else {
current = next;
}
return element;
}
@Override
public void clear() {
size = 0;
first = null;
last = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
// size == 0
// index == 0
// 往最后面添加元素
if (index == size) {
Node<E> oldLast = last;
last = new Node<>(oldLast, element, first);
// 这是链表添加的第一个元素
if (oldLast == null) {
first = last;
first.next = first;
first.prev = first;
} else {
oldLast.next = last;
first.prev = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
prev.next = node;
// index == 0
if (next == first) {
first = node;
}
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
return remove(node(index));
}
private E remove(Node<E> node) {
if (size == 1) {
first = null;
last = null;
} else {
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
// index == 0
if (node == first) {
first = next;
}
// index == size - 1
if (node == last) {
last = prev;
}
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) {
return i;
}
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) {
return i;
}
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 获取index位置对应的节点对象
*
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
//1.如果index小于链表容量的一半，则从首元素开始向后查找
if (index < (size >> 1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
//2.index大于链表容量的一半，从尾元素向前查找
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.element);
} else {
sb.append("null");
}
sb.append("_").append(element).append("_");
if (next != null) {
sb.append(next.element);
} else {
sb.append("null");
}
return sb.toString();
}
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 maiblog
阅读建议
评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
最新评论
评论模块未完成
liuzhihang /
