链表
1. 定义：链表通常由一连串节点组成，每个节点包含任意的实例数据和一个或两个用来指向上一个/下一个节点的位置的链接
2. 存储结构：链表(Linked List)是一种常见的基础数据结构，是一种线性表，但是不会按线性的顺序存储数据，而是在每一个节点上存放下一个节点的指针(Pointer)
3. 特征：使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，灵活的内存动态管理。但是链表失去了数组随机读取的有点，同时链表由于增加了结点的指针域，空间开销较大。
单链表
说明：
单链表的节点(Node)分为两部分，第一部分数据域(data)保存节点数据信息，另一部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
代码实现
package com.hulm.link;
/**
* 单链表
*/
public class SingleLinked<T> {
// 链表对象类
@SuppressWarnings("hiding")
private class Node<T> {
// 当前节点数据
private T data;
// 下一个节点
private Node<T> next;
// 初始化一个节点
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
// 获取节点数据
public T getData() {
return data;
}
}
// 头节点
private Node<T> head;
// 链表的长度
private int size;
// 构造器初始化链表
public SingleLinked() {
this.head = null;
this.size = 0;
}
// 判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
// 获取链表的长度
public int size() {
return size;
}
// 在链表的末尾插入一个元素
public void add(T e) {
// 如果链表为空，把数据插入到头节点
if (isEmpty()) {
head = new Node<T>(e, null);
head.next = null;
} else {
// 获取头节点
Node<T> temp = head;
// 遍历向后查找，查找到最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node<T>(e, null);
}
size++;
}
// 在指定位置添加
public void insert(int index, T e) {
if (index < 0 || index > size()) {
throw new ArrayIndexOutOfBoundsException("插入位置不合法");
}
// 如果节点为头节点
if (index == 0) {
Node<T> temp = head;
head = new Node<T>(e, temp);
} else if (index < size()) {
// 获取指定位置的上一个节点
Node<T> temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
Node<T> preNode = temp;
// 获取当前节点
Node<T> currNode = getNode(index);
// 创建要插入的节点
Node<T> insertNode = new Node<T>(e, currNode);
// 将上一个节点的next节点指向当前节点的下一个节点
preNode.next = insertNode;
// 在尾部插入节点
} else {
// 获取头节点
Node<T> temp = head;
// 遍历向后查找，查找到最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node<T>(e, null);
}
size++;
}
// 获取指定位置元素节点
private Node<T> getNode(int index) {
// 检查位置是否合法
checkPosition(index);
Node<T> temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
// 获取指定位置的节点数据
public T get(int index) {
return getNode(index).getData();
}
// 删除指定位置元素
public void remove(int index) {
// 验证位置是否合法
checkPosition(index);
// 如果节点为头节点
if (index == 0) {
head = head.next;
} else {
// 获取指定位置的上一个节点
Node<T> temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
Node<T> preNode = temp;
// 获取下一个节点
Node<T> nextNode = getNode(index).next;
// 将上一个节点的next节点指向当前节点的下一个节点
preNode.next = nextNode;
}
size--;
}
// 判断位置是否合法
public void checkPosition(int index) {
// 如果输入的位置小于0获取大于size-1,则返回越界异常
if (index < 0 || index > size() - 1) {
throw new ArrayIndexOutOfBoundsException("位置不合法");
}
}
// 重写toString方法
public String toString() {
if (size() == 0) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
// 获取头节点
Node<T> temp = head;
// 遍历向后查找，查找到最后一个节点
while (temp.next != null) {
sb.append(temp.getData() + ", ");
temp = temp.next;
}
sb.append(temp.getData());
sb.append("]");
return sb.toString();
}
}
}
单链表的测试类
package com.hulm.link;
public class TestSingleLinked {
public static void main(String[] args) {
SingleLinked<Integer> sl = new SingleLinked<Integer>();
sl.add(1);
sl.add(2);
sl.add(4);
sl.add(5);
System.out.println(sl);
System.out.println(sl.get(3));
System.out.println(sl);
sl.remove(2);
System.out.println(sl);
sl.insert(1, 11);
System.out.println(sl);
sl.insert(0, 0);
System.out.println(sl);
System.out.println(sl.get(4));
sl.insert(5, 22);
System.out.println(sl);
}
}
双链表
双链表的节点(Node)分为三部分，第一部分存储上一个节点的地址，第二部分数据域(data)保存节点数据信息，第三部分存储下一个节点的地址。第一个节点的上一个节点地址指向空值，最后一个节点存储地址的部分指向空值。
双链表的实现
package com.hulm.link;
/**
* 双链表
*/
public class DoubleLinked<T> {
// 链表对象类
@SuppressWarnings("hiding")
private class Node<T> {
// 前一个节点
private Node<T> prev;
// 当前节点数据
private T data;
// 下一个节点
private Node<T> next;
// 初始化一个节点
public Node(Node<T> prev, T data, Node<T> next) {
this.prev = prev;
this.data = data;
this.next = next;
}
// 获取节点数据
public T getData() {
return data;
}
}
// 头节点
private Node<T> head;
// 尾部节点
private Node<T> tail;
// 链表的长度
private int size;
// 构造器初始化链表
public DoubleLinked() {
this.head = tail = null;
this.size = 0;
}
// 判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
// 获取链表的长度
public int size() {
return size;
}
// 在链表的末尾插入一个元素
public void add(T e) {
// 如果链表为空，把数据插入到头节点
if (isEmpty()) {
head = new Node<T>(null, e, tail);
head.next = null;
} else {
// 获取头节点
Node<T> temp = head;
// 遍历向后查找，查找到最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node<T>(temp, e, null);
tail = temp.next;
}
size++;
}
// 在指定位置添加
public void insert(int index, T e) {
if (index < 0 || index > size()) {
throw new ArrayIndexOutOfBoundsException("插入位置不合法");
}
// 如果节点为头节点
if (index == 0) {
Node<T> temp = head;
head = new Node<T>(null, e, temp);
temp.prev = head;
} else if (index < size()) {
// 获取指定位置的上一个节点
Node<T> temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
Node<T> preNode = temp;
// 获取当前节点
Node<T> currNode = getNode(index);
// 创建要插入的节点
Node<T> insertNode = new Node<T>(preNode, e, currNode);
// 将上一个节点的next节点指向当前节点的下一个节点
preNode.next = insertNode;
currNode.prev = insertNode;
// 在尾部插入节点
} else {
// 获取头节点
Node<T> temp = tail;
// 要插入的节点
Node<T> insertNode = new Node<T>(temp, e, null);
temp.next = insertNode;
}
size++;
}
// 获取指定位置元素节点
private Node<T> getNode(int index) {
// 检查位置是否合法
checkPosition(index);
// 定义链表的中间位置
int mid = size >> 1;
// 定义临时节点
Node<T> temp = null;
// 如果位置在mid之前
if (index <= mid) {
temp = head;
for (int i = 0; i < mid; i++) {
temp = temp.next;
}
// 如果位置在mid之后
} else if (index > mid) {
temp = tail;
for (int i = size() - 1; i > mid; i--) {
temp = temp.prev;
}
}
return temp;
}
// 获取指定位置的节点数据
public T get(int index) {
return getNode(index).getData();
}
// 删除指定位置元素
public void remove(int index) {
// 验证位置是否合法
checkPosition(index);
// 如果节点为头节点
if (index == 0) {
head = head.next;
} else {
// 获取指定位置的上一个节点
Node<T> temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
Node<T> preNode = temp;
// 获取下一个节点
Node<T> nextNode = getNode(index).next;
// 将上一个节点的next节点指向当前节点的下一个节点
preNode.next = nextNode;
}
size--;
}
// 判断位置是否合法
public void checkPosition(int index) {
// 如果输入的位置小于0获取大于size-1,则返回越界异常
if (index < 0 || index > size() - 1) {
throw new ArrayIndexOutOfBoundsException("位置不合法");
}
}
// 重写toString方法
public String toString() {
if (size() == 0) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
// 获取头节点
Node<T> temp = head;
// 遍历向后查找，查找到最后一个节点
while (temp.next != null) {
sb.append(temp.getData() + ", ");
temp = temp.next;
}
sb.append(temp.getData());
sb.append("]");
return sb.toString();
}
}
}
##双链表的测试类
package com.hulm.link;
public class TestDoubleLinked {
public static void main(String[] args) {
DoubleLinked<Integer> sl = new DoubleLinked<Integer>();
sl.add(1);
sl.add(2);
sl.add(4);
sl.add(5);
System.out.println(sl);
System.out.println(sl.get(3));
System.out.println(sl);
sl.remove(2);
System.out.println(sl);
sl.insert(1, 11);
System.out.println(sl);
sl.insert(0, 0);
System.out.println(sl);
System.out.println(sl.get(4));
sl.insert(5, 22);
System.out.println(sl);
}
}
作者：宿命__胡
来源：CSDN
原文：https://blog.csdn.net/zhushao_1229/article/details/87905538
版权声明：本文为博主原创文章，转载请附上博文链接！