线性数据结构之链表
单链表
由各个节点通过一个Next引用链接在一起组成,每一个节点都存在后继节点(链尾除外),内存结构由数据域和Next 引用组成。
双向链表
由各个节点通过Next引用和 Prev引用链接在一起组成,每一个内存结构都存在前驱节点和后继节点(链头没有前驱,链尾没有后继),节点由数据域、Prev引用和 Next引用组成。
单向循环链表
由各个节点通过一个 Next引用 链接在一起组成,每一个节点都存在后继节点,节点由数据域和 Next 引用组成。
双向循环链表
由各个节点通过Next引用 和Prev引用 链接在一起组成,每一个内存结构都存在前驱节点和后继节点,节点由数据域、Prev引用和Next引用组成。
链表VS数组
底层存储结构上
数组需要一组连续的内存空间存储数据,而链表恰恰相反它并不需要连续的内存空间。
性能上
数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别,它们插入、删除、随机访问操作的时间复杂度正好相反
实现单链表
/** * 单向链表
*/
public class SingleDirectLinkedList<E> {
//链表大小
private int size;
//链表的头结点
private ListNode<E> head;
/**
* 查询链表大小
* @return
*/
public int getSize(){
return size;
}
/**
* 链表初始化
*/
public SingleDirectLinkedList() {
this.size = 0;
this.head = new ListNode(null);
}
/**
* 在指定位置插入节点
* @param index
* @param val
*/
public void add(int index,E val){
//检查插入的位置下标
if(index < 0 || index > size)
throw new RuntimeException("插入位置不存在");
ListNode listNode = new ListNode(val);
ListNode curr = head;
ListNode after = null;
//查找插入节点的前置节点
for (int i = 0; i < index ; i++)
curr = curr.next;
//查找插入节点的后置节点
if(curr != null)
after = curr.next;
//插入
listNode.next = after;
curr.next = listNode;
size++;
}
/**
* 删除指定下标位置的节点
* @param index 下标位置信息
*/
public void del(int index){
ListNode prev = head;
ListNode curr = null;
ListNode after = null;
if(index < 0 || index > size)
throw new RuntimeException("删除位置不存在")
//被删除节点的前置节点
for (int i = 0; i < index - 1 ; i++) {
prev = prev.next;
}
//被删除节点
curr = prev.next;
//被删除节点的后置节点
if(curr.next != null)
after = curr.next;
//删除节点
prev.next = after;
curr = null;
size --;
}
class ListNode<E>{
private E val;
private ListNode<E> next;
public ListNode(E val) {
this.val = val;
}
}
}
链表和数组相比可能略显复杂一点,由单链表衍生出来的链表种类也在上面一一列举出来了,文章中也对数组和链表的相关操作的性能做了一些比较,在日常开发中,可以根据使用场景以及性能要求来选择使用。
以上是 线性数据结构之链表 的全部内容, 来源链接: utcz.com/z/514339.html