数据结构之双向链表

导读:本篇文章讲解 数据结构之双向链表,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

目录

  • 一、双向链表是什么?
  • 二、双向链表自实现
  •         1.node方法
  •         2.add
  •         3.remove
  •         4.clear分析
  • 三、双向链表 vs 单向链表
  • 四、双向链表 vs 动态数组

一、双向链表是什么?

使用双向链表是可以提升链表的综合性能的。一张图就可以表示得很清楚了

fc93e5ad0eba4117aa324780da3790f2.png

 

二、双向链表自实现

1.node方法(根据下标查找元素)

private Node<E> node(int index) {
		rangeCheck(index);//这是自己封装的一个检查函数,用来检查index的合法性,否则抛出异常
		
		if (index < (size >> 1)) {
			Node<E> node = first;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
			return node;
		} else {
			Node<E> node = last;
			for (int i = size - 1; i > index; i--) {
				node = node.prev;
			}
			return node;
		}
	}

根据下标找出对应的节点,如果是单链表,则要从头到尾挨个找,但是对于双链表,我们可以先判断下标索引值与链表长度的一半进行对比,如果小于长度的一半,则可以从链表的头开始查找,如果大于了长度的一半,则可以从尾开始查找。

2.add (添加元素)

8261971ff61f40c0b1c4c577019cddd6.png

public void add(int index, E element) {
		rangeCheckForAdd(index); //这是自己封装的一个检查函数,用来检查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;
			
			if (prev == null) { // index == 0
				first = node;
			} else {
				prev.next = node;
			}
		}
		
		size++;
	}

3.remove(删除元素)

public E remove(int index) {
		rangeCheck(index); //这是自己封装的一个检查函数,用来检查index的合法性,否则抛出异常

		Node<E> node = node(index);
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		
		if (prev == null) { // index == 0
			first = next;
		} else {
			prev.next = next;
		}
		
		if (next == null) { // index == size - 1
			last = prev;
		} else {
			next.prev = prev;
		}
		
		size--;
		return node.element;
	}

  4.clear分析 

2b759167c80d4b8fa7dadb2861425903.png

	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

 按照之前咱们一般的理解,此时虽然已经把first和last置空了,与链表失去了联系,但是链表中的各个节点都相互指向,都被引用着,所以认为此时双链表不会被JVM回收。错了!!!此时链表相互指向的引线的性质已经变了,他们已经不再是gc root对象了。对于什么是gc root对象,简单的理解就是在栈中被局部变量指向的对象。所以此时clear这个函数是可以的。

 

三、双向链表 vs 单向链表 

 粗略对比一下删除的操作数量:


单向链表:1 + 2 + 3 + … + n = (1+n) ∗ n/ 2 = n/2 + n^2/2 ,除以n平均一下是 1/2 + n/2

双向链表:(1 + 2 + 3 + … + n/2 ) * 2 = ((1+ n/2)∗ n/2 )/2 * 2 = n/2 + n^2/4,除以n平均一下是 1/2 + n/4
经过对比,操作数量减少了一半
 

四、双向链表 vs 动态数组 

 
◼动态数组:开辟、销毁内存空间的次数相对较少,但可能造成内存空间浪费
◼ 双向链表:开辟、销毁内存空间的次数相对较多,但不会造成内存空间的浪费
◼ 如果频繁在尾部进行添加、删除操作,动态数组、双向链表均可选择
◼ 如果频繁在头部进行添加、删除操作,建议选择使用双向链表
◼ 如果有频繁的(在任意位置)添加、删除操作,建议选择使用双向链表
◼ 如果有频繁的查询操作(随机访问操作),建议选择使用动态数组

 

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/94605.html

(0)
小半的头像小半

相关推荐

极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!