这次牛逼了,面试字节被问LinkedList原理了!手足无措啊
概述
LinkedList底層是基于鏈表實(shí)現(xiàn)。鏈表沒有長度限制,內(nèi)存地址不需要固定長度,也不需要是連續(xù)的地址來進(jìn)行存儲,只需要通過引用來關(guān)聯(lián)前后元素即可完成整個(gè)鏈表的連續(xù)。所以鏈表的優(yōu)點(diǎn)就是添加刪除元素比較快,只需要移動指針,并且不需要判斷擴(kuò)容。缺點(diǎn)就是因?yàn)闆]有索引,所以在查詢和遍歷元素時(shí)候比較慢。
使用場景:在增刪操作使用較多,查詢遍歷操作使用較少情況下比較適合去使用;例如:拿來當(dāng)棧使用。
數(shù)據(jù)結(jié)構(gòu)
繼承實(shí)現(xiàn)關(guān)系
1 public class LinkedList<E> 2 extends AbstractSequentialList<E> 3 implements List<E>, Deque<E>, Cloneable, java.io.Serializable- AbstractSequentialList:本質(zhì)上面與繼承AbstractList 沒有什么區(qū)別,AbstractSequentialList完善了 AbstractList中沒有實(shí)現(xiàn)的方法。
- List:實(shí)現(xiàn)List接口。
- Deque:實(shí)現(xiàn)Deque隊(duì)列接口,擁有作為雙端隊(duì)列(隊(duì)列和棧)的功能。
- Cloneable:重寫clone()方法,通過創(chuàng)建新的LinkedList 對象,遍歷拷貝數(shù)據(jù)進(jìn)行對象拷貝。
- Serializable:重寫read/writeObject() 方法實(shí)現(xiàn)序列化。
靜態(tài)內(nèi)部類
為什么Node這個(gè)類是靜態(tài)的?答案是:這跟內(nèi)存泄露有關(guān),Node類是在LinkedList類中的,也就是一個(gè)內(nèi)部類,若不使用static修飾,那么Node就是一個(gè)普通的內(nèi)部類,在java中,一個(gè)普通內(nèi)部類在實(shí)例化之后,默認(rèn)會持有外部類的引用,這就有可能造成內(nèi)存泄露(內(nèi)部類與外部類生命周期不一致時(shí))。但使用static修飾過的內(nèi)部類(稱為靜態(tài)內(nèi)部類),就不會有這種問題?!精@取資料】
- 非靜態(tài)內(nèi)部類會自動生成一個(gè)構(gòu)造器依賴于外部類:也是內(nèi)部類可以訪問外部類的實(shí)例變量的原因。
- 靜態(tài)內(nèi)部類不會生成,訪問不了外部類的實(shí)例變量,只能訪問類變量。
基本屬性
// 元素?cái)?shù)量 2 transient int size = 0; 3 // 頭結(jié)點(diǎn) 4 transient Node<E> first; 5 // 尾節(jié)點(diǎn) 6 transient Node<E> last;構(gòu)造方法
1 public LinkedList() { 2 } 3 4 public LinkedList(Collection<? extends E> c) { 5 this(); 6 addAll(c); 7 }主要方法解析
獲取元素
peek():隊(duì)列的查,獲取隊(duì)頭元素。
public E get(int index) { // 根據(jù)索引獲取checkElementIndex(index);return node(index).item;}Node<E> node(int index) {// assert isElementIndex(index);// 利用二分法查找;小于中間數(shù)從頭結(jié)點(diǎn)開始找,否則從尾節(jié)點(diǎn)開始找//加入Java開發(fā)交流君樣:756584822一起吹水聊天if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}// 獲取隊(duì)頭元素 ,但是不刪除隊(duì)列的頭元素(雙端隊(duì)列Deque中的方法)public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}// 獲取隊(duì)尾元素,但是不刪除隊(duì)列的尾元素(實(shí)現(xiàn)雙端隊(duì)列Deque中的方法)public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}// 隊(duì)列的查。獲取隊(duì)頭元素。public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}添加元素
offer():隊(duì)列的增,添加隊(duì)尾元素,底層實(shí)現(xiàn)是調(diào)用add()->linkLast()。
push():棧的增,把元素壓入棧中,添加對頭元素,底層實(shí)現(xiàn)是調(diào)用addFirst()->linkFirst()。
1 // 添加元素,默認(rèn)在鏈表尾部添加2 public boolean add(E e) {3 linkLast(e);4 return true;5 }//加入Java開發(fā)交流君樣:756584822一起吹水聊天6 // 指定索引添加元素7 public void add(int index, E element) {8 checkPositionIndex(index); // 檢驗(yàn)下標(biāo)是否越界9 10 if (index == size) // 如果要插入的索引等于現(xiàn)有元素長度,說明是要在尾部插入元素 11 linkLast(element); 12 else // 否則,獲取該索引節(jié)點(diǎn),在該節(jié)點(diǎn)之前插入元素 13 linkBefore(element, node(index)); 14 } 15 16 public boolean addAll(Collection<? extends E> c) { 17 return addAll(size, c); 18 } 19 public boolean addAll(int index, Collection<? extends E> c) { 20 checkPositionIndex(index); // 檢驗(yàn)下標(biāo)是否越界 21 22 Object[] a = c.toArray(); 23 int numNew = a.length; 24 if (numNew == 0) 25 return false; 26 27 // pred:前置節(jié)點(diǎn),在該節(jié)點(diǎn)之后插入元素。succ:該索引位節(jié)點(diǎn)。 28 Node<E> pred, succ; 29 if (index == size) { 30 succ = null; 31 pred = last; 32 } else { 33 succ = node(index); 34 pred = succ.prev; 35 } 36 // 將數(shù)組設(shè)置為鏈表 37 for (Object o : a) { 38 @SuppressWarnings("unchecked") E e = (E) o; 39 Node<E> newNode = new Node<>(pred, e, null); // 新建一個(gè)節(jié)點(diǎn),指向前置節(jié)點(diǎn) 40 if (pred == null) // 如果前置節(jié)點(diǎn)為空,說明該鏈表為空。將頭節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn) 41 first = newNode; 42 else // 前置節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn) 43 pred.next = newNode; 44 pred = newNode; // 將當(dāng)前節(jié)點(diǎn)設(shè)置為前置節(jié)點(diǎn),供后面需要插入的節(jié)點(diǎn)使用 45 }//加入Java開發(fā)交流君樣:756584822一起吹水聊天 46 47 if (succ == null) { 48 last = pred; 49 } else { 50 pred.next = succ; 51 succ.prev = pred; 52 } 53 54 size += numNew; 55 modCount++; 56 return true; 57 } 58 59 // 添加元素到頭結(jié)點(diǎn)(實(shí)現(xiàn)雙端隊(duì)列Deque中的方法) 60 public void addFirst(E e) { 61 linkFirst(e); 62 } 63 private void linkFirst(E e) { 64 final Node<E> f = first; // 原頭節(jié)點(diǎn) 65 final Node<E> newNode = new Node<>(null, e, f); // 新建一個(gè)節(jié)點(diǎn),要添加的元素 66 first = newNode; // 將頭結(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 67 if (f == null) // 如果原頭結(jié)點(diǎn)為空,說明原鏈表為空。這是添加的第一個(gè)元素,將尾結(jié)點(diǎn)也指向該新建的節(jié)點(diǎn) 68 last = newNode; 69 else // 如果原頭結(jié)點(diǎn)不為空,則將原頭結(jié)點(diǎn)的前置節(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 70 f.prev = newNode; 71 size++; // 元素?cái)?shù)量+1 72 modCount++; // 修改次數(shù)+1 73 } 74 // 添加元素到尾結(jié)點(diǎn)(實(shí)現(xiàn)雙端隊(duì)列Deque中的方法) 75 public void addLast(E e) { 76 linkLast(e); 77 } 78 void linkLast(E e) { 79 final Node<E> l = last; // 原尾結(jié)點(diǎn) 80 final Node<E> newNode = new Node<>(l, e, null); // 新建一個(gè)節(jié)點(diǎn),要添加的元素 81 last = newNode; // 將尾結(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 82 if (l == null) // 如果尾頭結(jié)點(diǎn)為空,說明原鏈表為空。這是添加的第一個(gè)元素,將頭結(jié)點(diǎn)也指向該新建的節(jié)點(diǎn) 83 first = newNode; 84 else // 如果原尾結(jié)點(diǎn)不為空,則將原尾結(jié)點(diǎn)的后繼節(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 85 l.next = newNode; 86 size++; // 元素?cái)?shù)量+1 87 modCount++; // 修改次數(shù)+1 88 } 89 90 // 隊(duì)列的添加方法 91 public boolean offer(E e) { 92 return add(e); 93 } 94 95 // 棧的添加方法 96 public void push(E e) { 97 addFirst(e); 98 }刪除元素
poll():隊(duì)列的刪,獲取對頭元素并且對頭元素刪除。
pop():棧的刪,返回的是棧頂元素并將棧頂元素刪除。
1 public boolean remove(Object o) {2 if (o == null) {3 for (Node<E> x = first; x != null; x = x.next) {4 if (x.item == null) {5 unlink(x);6 return true;7 }8 }9 } else { 10 for (Node<E> x = first; x != null; x = x.next) { 11 if (o.equals(x.item)) { 12 unlink(x); 13 return true; 14 } 15 } 16 } 17 return false; 18 } 19 public E remove(int index) { 20 checkElementIndex(index); 21 return unlink(node(index)); 22 } 23 // 將該節(jié)點(diǎn)前置節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)后繼節(jié)點(diǎn),將該節(jié)點(diǎn)后繼節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)前置節(jié)點(diǎn)。并將該節(jié)點(diǎn)置為空 24 E unlink(Node<E> x) { 25 // assert x != null; 26 final E element = x.item; 27 final Node<E> next = x.next; 28 final Node<E> prev = x.prev; 29 30 if (prev == null) { 31 first = next; 32 } else { 33 prev.next = next; 34 x.prev = null; 35 } 36 37 if (next == null) { 38 last = prev; 39 } else { 40 next.prev = prev; 41 x.next = null; 42 } 43 44 x.item = null; 45 size--; 46 modCount++; 47 return element; 48 } 49 // 將頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)設(shè)置為新的頭結(jié)點(diǎn),并將原頭節(jié)點(diǎn)置為空 50 private E unlinkFirst(Node<E> f) { 51 // assert f == first && f != null; 52 final E element = f.item; 53 final Node<E> next = f.next; 54 f.item = null; 55 f.next = null; // help GC 56 first = next; 57 if (next == null) 58 last = null; 59 else 60 next.prev = null; 61 size--; 62 modCount++; 63 return element; 64 } 65 //加入Java開發(fā)交流君樣:756584822一起吹水聊天 66 // 將尾結(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)設(shè)置為新的尾結(jié)點(diǎn),并將原尾節(jié)點(diǎn)置為空 67 private E unlinkLast(Node<E> l) { 68 // assert l == last && l != null; 69 final E element = l.item; 70 final Node<E> prev = l.prev; 71 l.item = null; 72 l.prev = null; // help GC 73 last = prev; 74 if (prev == null) 75 first = null; 76 else 77 prev.next = null; 78 size--; 79 modCount++; 80 return element; 81 } 82 83 public E remove() { 84 return removeFirst(); 85 } 86 87 // 隊(duì)列的刪除方法 88 public E poll() { 89 final Node<E> f = first; 90 return (f == null) ? null : unlinkFirst(f); 91 } 92 // 棧的刪除方法 93 public E pop() { 94 return removeFirst(); 95 }最后,祝大家早日學(xué)有所成,拿到滿意offer
總結(jié)
以上是生活随笔為你收集整理的这次牛逼了,面试字节被问LinkedList原理了!手足无措啊的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 股票分红10派几是什么意思?
- 下一篇: 花呗评估被暂停使用要多久才能恢复