线性数据结构之链表

编程

单链表

由各个节点通过一个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

回到顶部