赞
踩
原文地址:https://blog.csdn.net/qq_32575047/article/details/78885066
今天继续分享一道Java经典面试题:
题目描述:Java 中的 LinkedList 是单向链表还是双向链表?
是双向链表,你可以检查 JDK 的源码。在 Eclipse,你可以使用快捷键 Ctrl + T,直接在编辑器中打开该类。
于是对于LinkedList的实现做了进一步的探索,得到了这些知识(注:看懂下面的知识需要一些数据结构的知识):
Linkedlist,双向链表,优点,增加删除,用时间很短,但是因为没有索引,对索引的操作,比较麻烦,只能循环遍历,但是每次循环的时候,都会先判断一下,这个索引位于链表的前部分还是后部分,每次都会遍历链表的一半 ,而不是全部遍历。
双向链表,都有一个previous和next, 链表最开始的部分都有一个fiest和last 指向第一个元素,和最后一个元素。增加和删除的时候,只需要更改一个previous和next,就可以实现增加和删除,所以说,LinkedList对于数据的删除和增加相当的方便。
熟悉链表算法就知道是什么原因,接下来详细讲解一下链表算法,首先给大家看一下我简单实现的链表node:
- class LinkNode<T> {
- public LinkNode(LinkNode<T> next, LinkNode<T> previous, T obj) {
- this.next = next;
- this.previous = previous;
- this.obj = obj;
- }
-
- private LinkNode<T> next;//下一个节点
-
- private LinkNode<T> previous;//上一个节点
- private T obj;
- /**
- * 删除节点
- */
- public void remove() {
- next.previous = previous;
- previous.next = next;
-
- }
- /**
- * 修改节点
- */
- public void set(T t) {
- LinkNode<T> link = new LinkNode<T>(next, previous, t);
- next.previous = link;
- previous.next = link;
- }
-
- public String toString() {
- return obj.toString();
- }
- }
从这段代码可以看出:
1、当前对象保存着上一个和下一个对象的引用
- private LinkNode<T> next;//下一个节点
-
- private LinkNode<T> previous;//上一个节点
2、remove一个对象(这里有点不好理解,你可以把链表想成一个锁链,形象思维。):
2.1、当前对象的previous对象的next对先指向的当前对象next。
2.2、当前对象的next对象previous指向当前对先previous。
- next.previous = previous;//前与后相连
- previous.next = next;//后与前相连
这样就实际上把要删除的对象挤出链接里了。
3、set一个对象(理解删除这里就比较好理解):
1、创建一个新对象,这个对象的next和previous与当前对象相同。
2、把this.next.previous指向新创建的对象。
3、把this.previous.next指向新创建的对象。
- public void set(T t) {
- LinkNode<T> link = new LinkNode<T>(next, previous, t);//新对象
- next.previous = link;//改变next
- previous.next = link;//改变previous
- }
这样这个对象就被替换掉了。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。