java实现单链表和双链表数据结构
程序员文章站
2024-03-16 15:30:16
...
首先定义一个接口, 规范单链表和双链表常用的基本操作:
/**
* @Author Huzz
* @Created 2021-10-09 17:49
*/
public interface LinkedList<T> {
/**
* 节点长度
* @return
*/
int size();
/**
* 返回链表是否为空
* @return 空:true | 非空:false
*/
boolean isEmpty();
/**
* 获取第index位置的节点的值
* @param index
* @return
*/
T get(int index);
/**
* 获取第1个节点的值
* @return
*/
T getFirst();
/**
* 获取最后一个节点的值
* @return
*/
T getLast();
/**
* 将节点插入到第index位置之前
* @param index
* @param data 数据
*/
void insert(int index, T data);
/**
* 将节点插入第一个节点处
* @param data 数据
*/
void insertFirst(T data);
/**
* 将节点追加到链表的末尾
* @param data
*/
void append(T data);
/**
* 删除index位置的节点
* @param index
*/
void del(int index);
/**
* 删除第一个节点
*/
void deleteFirst();
/**
* 删除最后一个节点
*/
void deleteLast();
}
单链表实现:
/**
* 单向链表
*
* @Author Huzz
* @Created 2021-10-09 14:49
*/
public class SingleLinkedList<T> implements LinkedList {
/**
* 表头
*/
private Node<T> nodeHead;
/**
* 节点个数
*/
private int nodeCount;
public SingleLinkedList() {
nodeHead = new Node(null, null);
nodeCount = 0;
}
/**
* 链表是否为空
*/
@Override
public boolean isEmpty() {
return nodeCount == 0;
}
/**
* 链表长度
*/
@Override
public int size() {
return nodeCount;
}
/**
* 查找节点
*
* @param index
* @return
*/
private Node<T> getNode(int index) {
if (nodeCount < 0 || index >= nodeCount) {
throw new IndexOutOfBoundsException();
}
Node<T> node = nodeHead.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 根据所给位置查找节点
*/
@Override
public T get(int index) {
return getNode(index).value;
}
/**
* 查找第一个节点
*
* @return
*/
@Override
public T getFirst() {
return getNode(0).value;
}
/**
* 查找最后一个节点
*
* @return
*/
@Override
public T getLast() {
return getNode(nodeCount - 1).value;
}
/**
* 在指定位置前插入节点
*
* @param index
* @param data
*/
@Override
public void insert(int index, Object data) {
if (index == 0) {
Node<T> node = new Node<>(nodeHead.next, (T) data);
nodeHead.next = node;
nodeCount++;
return;
}
Node lNode = getNode(index - 1);
Node<T> node = new Node<>(lNode.next, (T) data);
lNode.next = node;
nodeCount++;
return;
}
/**
* 在链表末尾添加节点
*
* @param data
*/
@Override
public void append(Object data) {
insert(nodeCount, (T) data);
}
/**
* 在第一个节点前插入一个节点
*
* @param data
*/
@Override
public void insertFirst(Object data) {
insert(0, (T) data);
}
/**
* 删除节点
*
* @param index
*/
@Override
public void del(int index) {
Node node = getNode(index);
if (index == 0) {
nodeHead.next = node.next;
node = null;
nodeCount--;
return;
}
getNode(index - 1).next = node.next;
node = null;
nodeCount--;
return;
}
/**
* 删除第一个节点
*/
@Override
public void deleteFirst() {
del(0);
}
/**
* 删除最后一个节点
*/
@Override
public void deleteLast() {
del(nodeCount - 1);
}
/**
* ======================================定义节点==============================================
*/
/**
* 单链表节点定义
*
* @param <T>
*/
private class Node<T> {
// 后继
private Node<T> next;
// 数据
private T value;
public Node(Node next, T data) {
this.next = next;
this.value = data;
}
}
/** =========================================================================================== */
}
双链表实现:
/**
* 双向链表
*
* @Author Huzz
* @Created 2021-10-09 8:54
*/
public class DoubleLinkedList<T> implements LinkedList {
/**
* 表头
*/
private Node<T> nodeHead;
/**
* 节点个数
*/
private int nodeCount;
/**
* 构造函数
*/
public DoubleLinkedList() {
// 初始化链表, 创建表头(表头不存储数据)
nodeHead = new Node<T>(null, null, null);
// 初始化前驱和后继, 默认指向自身
nodeHead.prev = nodeHead.next = nodeHead;
// 初始化节点个数, 0个
nodeCount = 0;
}
/**
* 节点长度
*
* @return
*/
@Override
public int size() {
return nodeCount;
}
/**
* 返回链表是否为空
*
* @return 空:true | 非空:false
*/
@Override
public boolean isEmpty() {
return nodeCount == 0;
}
/**
* 获取第index位置的节点
*
* @param index
* @return
*/
private Node<T> getNode(int index) {
if (index < 0 || index >= nodeCount) {
throw new IndexOutOfBoundsException();
}
if (index <= nodeCount / 2) {
/* 正向查找 */
// 初始化指向第一个Node
Node<T> node = nodeHead.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
/*反向查找*/
// 初始化指向最后一个Node
Node<T> rNode = nodeHead.prev;
// 查找范围长度
int rLength = nodeCount - index - 1;
for (int j = 0; j < rLength; j++) {
rNode = rNode.prev;
}
return rNode;
}
}
/**
* 获取第index位置的节点的值
*
* @param index
* @return
*/
@Override
public T get(int index) {
return getNode(index).value;
}
/**
* 获取第1个节点的值
*
* @return
*/
@Override
public T getFirst() {
return getNode(0).value;
}
/**
* 获取最后一个节点的值
*
* @return
*/
@Override
public T getLast() {
return getNode(nodeCount - 1).value;
}
/**
* 将节点插入到第index位置之前
*
* @param index
* @param data
*/
@Override
public void insert(int index, Object data) {
// 若初始化时除头节点外没有其他节点
if (index == 0) {
// 新建节点
Node<T> node = new Node<>(nodeHead, nodeHead.next, (T) data);
nodeHead.next = node;
node.next.prev = node;
nodeCount++;
return;
}
Node<T> inode = getNode(index);
Node<T> tNode = new Node<>(inode.prev, inode, (T) data);
inode.prev.next = tNode;
inode.prev = tNode;
nodeCount++;
return;
}
/**
* 将节点插入第一个节点处
*
* @param data
*/
@Override
public void insertFirst(Object data) {
insert(0, (T) data);
}
/**
* 将节点追加到链表的末尾
*
* @param data
*/
@Override
public void append(Object data) {
Node<T> node = new Node<>(nodeHead.prev, nodeHead, (T) data);
nodeHead.prev.next = node;
nodeHead.prev = node;
nodeCount++;
}
/**
* 删除index位置的节点
*
* @param index
*/
@Override
public void del(int index) {
Node<T> node = getNode(index);
node.prev.next = node.next;
node.next.prev = node.prev;
node = null;
nodeCount--;
}
/**
* 删除第一个节点
*/
@Override
public void deleteFirst() {
del(0);
}
/**
* 删除最后一个节点
*/
@Override
public void deleteLast() {
del(nodeCount - 1);
}
/** ======================================定义节点============================================== */
/**
* 双向链表节点定义
*
* @param <T>
*/
private class Node<T> {
// 前驱
public Node prev;
// 后继
public Node next;
// 数据
public T value;
public Node(Node prev, Node next, T data) {
this.prev = prev;
this.next = next;
this.value = data;
}
}
/** =========================================================================================== */
}
使用:
/**
* @Author Huzz
* @Created 2021-10-09 18:51
*/
public class HuzzTest {
public static void main(String[] args) {
LinkedList<Integer> singleLinkedList = new SingleLinkedList<>();
LinkedList<Integer> doubleLinkedList = new DoubleLinkedList<>();
for (int i = 0; i < 10; i++) {
singleLinkedList.append(i);
doubleLinkedList.append(i);
}
singleLinkedList.append(45);
singleLinkedList.del(5);
singleLinkedList.isEmpty();
singleLinkedList.insertFirst(90);
doubleLinkedList.get(6);
doubleLinkedList.size();
}
}
虽然java提供了数据链表的工具类, 但自己学习过程中手工编写还是比较有收获的, 能加深对数据结构的认识.