中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

網(wǎng)站域名免費申請網(wǎng)站排名優(yōu)化培訓(xùn)哪家好

網(wǎng)站域名免費申請,網(wǎng)站排名優(yōu)化培訓(xùn)哪家好,剛剛好痛,做網(wǎng)站 php asp.net jsp文章目錄 概述LinkedList實現(xiàn)底層數(shù)據(jù)結(jié)構(gòu)構(gòu)造函數(shù)getFirst(), getLast()removeFirst(), removeLast(), remove(e), remove(index)add()addAll()clear()Positional Access 方法查找操作 概述 LinkedList同時實現(xiàn)了List接口和Deque接口,也就是說它既可以看作一個順序…

文章目錄

    • 概述
    • LinkedList實現(xiàn)
      • 底層數(shù)據(jù)結(jié)構(gòu)
      • 構(gòu)造函數(shù)
      • getFirst(), getLast()
      • removeFirst(), removeLast(), remove(e), remove(index)
      • add()
      • addAll()
      • clear()
      • Positional Access 方法
      • 查找操作

概述

LinkedList同時實現(xiàn)了List接口和Deque接口,也就是說它既可以看作一個順序容器,又可以看作一個隊列(Queue),同時又可以看作一個棧(Stack)。這樣看來,LinkedList簡直就是個全能冠軍。當(dāng)你需要使用?;蛘哧犃袝r,可以考慮使用LinkedList,一方面是因為Java官方已經(jīng)聲明不建議使用Stack類,更遺憾的是,Java里根本沒有一個叫做Queue的類(它是個接口名字)。關(guān)于?;蜿犃?#xff0c;現(xiàn)在的首選是ArrayDeque,它有著比LinkedList(當(dāng)作棧或隊列使用時)有著更好的性能。


LinkedList_base

LinkedList實現(xiàn)

底層數(shù)據(jù)結(jié)構(gòu)

LinkedList底層通過雙向鏈表實現(xiàn),本節(jié)將著重講解插入和刪除元素時雙向鏈表的維護過程。雙向鏈表的每個節(jié)點用內(nèi)部類Node表示。LinkedList通過firstlast引用分別指向鏈表的第一個和最后一個元素。當(dāng)鏈表為空的時候firstlast都指向null

    transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||*            (first.prev == null && first.item != null)*/transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||*            (last.next == null && last.item != null)*/transient Node<E> last;

其中Node是私有的內(nèi)部類:

    private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}

構(gòu)造函數(shù)

   /*** Constructs an empty list.*/public LinkedList() {}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param  c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public LinkedList(Collection<? extends E> c) {this();addAll(c);}

getFirst(), getLast()

獲取第一個元素, 和獲取最后一個元素:

    /*** Returns the first element in this list.** @return the first element in this list* @throws NoSuchElementException if this list is empty*/public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}/*** Returns the last element in this list.** @return the last element in this list* @throws NoSuchElementException if this list is empty*/public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}

removeFirst(), removeLast(), remove(e), remove(index)

remove()方法也有兩個版本,一個是刪除跟指定元素相等的第一個元素remove(Object o),另一個是刪除指定下標(biāo)處的元素remove(int index)。


LinkedList_remove.png

刪除元素 - 指的是刪除第一次出現(xiàn)的這個元素, 如果沒有這個元素,則返回false;判斷的依據(jù)是equals方法, 如果equals,則直接unlink這個node;由于LinkedList可存放null元素,故也可以刪除第一次出現(xiàn)null的元素;

    /*** Removes the first occurrence of the specified element from this list,* if it is present.  If this list does not contain the element, it is* unchanged.  More formally, removes the element with the lowest index* {@code i} such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>* (if such an element exists).  Returns {@code true} if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** @param o element to be removed from this list, if present* @return {@code true} if this list contained the specified element*/public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;}/*** Unlinks non-null node x.*/E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {// 第一個元素first = next;} else {prev.next = next;x.prev = null;}if (next == null) {// 最后一個元素last = prev;} else {next.prev = prev;x.next = null;}x.item = null; // GCsize--;modCount++;return element;}

remove(int index)使用的是下標(biāo)計數(shù), 只需要判斷該index是否有元素即可,如果有則直接unlink這個node。

    /*** Removes the element at the specified position in this list.  Shifts any* subsequent elements to the left (subtracts one from their indices).* Returns the element that was removed from the list.** @param index the index of the element to be removed* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E remove(int index) {checkElementIndex(index);return unlink(node(index));}

刪除head元素:

    /*** Removes and returns the first element from this list.** @return the first element from this list* @throws NoSuchElementException if this list is empty*/public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}/*** Unlinks non-null first node f.*/private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}

刪除last元素:

	/*** Removes and returns the last element from this list.** @return the last element from this list* @throws NoSuchElementException if this list is empty*/public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}/*** Unlinks non-null last node l.*/private E unlinkLast(Node<E> l) {// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}

add()

add()*方法有兩個版本,一個是add(E e),該方法在*LinkedList的末尾插入元素,因為有last指向鏈表末尾,在末尾插入元素的花費是常數(shù)時間。只需要簡單修改幾個相關(guān)引用即可;另一個是add(int index, E element),該方法是在指定下表處插入元素,需要先通過線性查找找到具體位置,然后修改相關(guān)引用完成插入操作。

    /*** Appends the specified element to the end of this list.** <p>This method is equivalent to {@link #addLast}.** @param e element to be appended to this list* @return {@code true} (as specified by {@link Collection#add})*/public boolean add(E e) {linkLast(e);return true;}/*** Links e as last element.*/void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}

LinkedList_add

add(int index, E element), 當(dāng)index==size時,等同于add(E e); 如果不是,則分兩步: 1.先根據(jù)index找到要插入的位置,即node(index)方法;2.修改引用,完成插入操作。

    /*** Inserts the specified element at the specified position in this list.* Shifts the element currently at that position (if any) and any* subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}

addAll()

addAll(index, c) 實現(xiàn)方式并不是直接調(diào)用add(index,e)來實現(xiàn),主要是因為效率的問題,另一個是fail-fast中modCount只會增加1次;

    /*** Appends all of the elements in the specified collection to the end of* this list, in the order that they are returned by the specified* collection's iterator.  The behavior of this operation is undefined if* the specified collection is modified while the operation is in* progress.  (Note that this will occur if the specified collection is* this list, and it's nonempty.)** @param c collection containing elements to be added to this list* @return {@code true} if this list changed as a result of the call* @throws NullPointerException if the specified collection is null*/public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}/*** Inserts all of the elements in the specified collection into this* list, starting at the specified position.  Shifts the element* currently at that position (if any) and any subsequent elements to* the right (increases their indices).  The new elements will appear* in the list in the order that they are returned by the* specified collection's iterator.** @param index index at which to insert the first element*              from the specified collection* @param c collection containing elements to be added to this list* @return {@code true} if this list changed as a result of the call* @throws IndexOutOfBoundsException {@inheritDoc}* @throws NullPointerException if the specified collection is null*/public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;Node<E> pred, succ;if (index == size) {succ = null;pred = last;} else {succ = node(index);pred = succ.prev;}for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;Node<E> newNode = new Node<>(pred, e, null);if (pred == null)first = newNode;elsepred.next = newNode;pred = newNode;}if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}

clear()

為了讓GC更快可以回收放置的元素,需要將node之間的引用關(guān)系賦空。

    /*** Removes all of the elements from this list.* The list will be empty after this call returns.*/public void clear() {// Clearing all of the links between nodes is "unnecessary", but:// - helps a generational GC if the discarded nodes inhabit//   more than one generation// - is sure to free memory even if there is a reachable Iteratorfor (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}first = last = null;size = 0;modCount++;}

Positional Access 方法

通過index獲取元素

    /*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {checkElementIndex(index);return node(index).item;}

將某個位置的元素重新賦值:

    /*** Replaces the element at the specified position in this list with the* specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}

將元素插入到指定index位置:

    /*** Inserts the specified element at the specified position in this list.* Shifts the element currently at that position (if any) and any* subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}

刪除指定位置的元素:

    /*** Removes the element at the specified position in this list.  Shifts any* subsequent elements to the left (subtracts one from their indices).* Returns the element that was removed from the list.** @param index the index of the element to be removed* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E remove(int index) {checkElementIndex(index);return unlink(node(index));}

查找操作

查找操作的本質(zhì)是查找元素的下標(biāo):

查找第一次出現(xiàn)的index, 如果找不到返回-1;

    /*** Returns the index of the first occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the lowest index {@code i} such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.** @param o element to search for* @return the index of the first occurrence of the specified element in*         this list, or -1 if this list does not contain the element*/public int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}

查找最后一次出現(xiàn)的index, 如果找不到返回-1;

    /*** Returns the index of the last occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the highest index {@code i} such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.** @param o element to search for* @return the index of the last occurrence of the specified element in*         this list, or -1 if this list does not contain the element*/public int lastIndexOf(Object o) {int index = size;if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;}

http://www.risenshineclean.com/news/22825.html

相關(guān)文章:

  • 做 愛 網(wǎng)站小視頻下載查詢網(wǎng)官網(wǎng)
  • 中石化第五建設(shè)有限公司官方網(wǎng)站濰坊關(guān)鍵詞優(yōu)化平臺
  • wordpress商家展示主題企業(yè)網(wǎng)站的優(yōu)化建議
  • 社區(qū)工作者優(yōu)化設(shè)計方法
  • 保定市住房和城鄉(xiāng)建設(shè)局網(wǎng)站競價廣告點擊軟件
  • 武漢黃浦醫(yī)院網(wǎng)站建設(shè)關(guān)鍵詞優(yōu)化排名平臺
  • 獨立做網(wǎng)站需要學(xué)什么條件關(guān)鍵詞優(yōu)化怎么寫
  • 做代購注冊什么網(wǎng)站搜索引擎優(yōu)化解釋
  • 臺州網(wǎng)站開發(fā)太原網(wǎng)站優(yōu)化公司
  • 學(xué)會了vue 能搭建一個網(wǎng)站平臺比較靠譜的電商培訓(xùn)機構(gòu)
  • jsp開發(fā)網(wǎng)站百度指數(shù)人群畫像哪里查詢
  • 網(wǎng)站備案的是域名還是空間電子商務(wù)網(wǎng)站建設(shè)與維護
  • 搭建網(wǎng)站難嗎電商培訓(xùn)學(xué)校
  • 玉溪做網(wǎng)站的公司seo的優(yōu)化步驟
  • 奪寶網(wǎng)站怎樣做優(yōu)化泰安做百度推廣的公司
  • 網(wǎng)站開發(fā)有什么點子軟文生成器
  • 公司主頁網(wǎng)站怎么做免費推廣軟件 推廣幫手
  • 服務(wù)器方面如何規(guī)劃建設(shè)網(wǎng)站外貿(mào)網(wǎng)站有哪些平臺
  • 政府門戶網(wǎng)站建設(shè)的基本意義有哪些網(wǎng)絡(luò)營銷的概念和特點是什么
  • 網(wǎng)站建設(shè)項目合同如何做好網(wǎng)絡(luò)推廣
  • 網(wǎng)站建設(shè)網(wǎng)站維護的具體內(nèi)容是什么seo推廣員是做什么的
  • 實際網(wǎng)站開發(fā)怎樣分工2023百度秒收錄技術(shù)
  • 北京環(huán)球影城每日客流量統(tǒng)計排名優(yōu)化公司口碑哪家好
  • 駐馬店廣告制作公司抖音seo教程
  • 自助建站系統(tǒng)個人網(wǎng)站怎樣開自己的網(wǎng)站
  • 產(chǎn)品網(wǎng)站用什么軟件做百度一下網(wǎng)頁首頁
  • 注冊城鄉(xiāng)規(guī)劃師報考條件提高seo排名
  • css做電商網(wǎng)站首頁株洲seo優(yōu)化首選
  • crm 都免費了城關(guān)網(wǎng)站seo
  • 搭建網(wǎng)站教程視頻查網(wǎng)站流量的網(wǎng)址