package com.nasuf.arraylist; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException; public class MyLinkedListimplements Iterable { private int theSize; private int modCount = 0; private Node beginMarker; private Node endMarker; private static class Node { public AnyType data; public Node prev; public Node next; public Node(AnyType d, Node p, Node n) { data = d; prev = p; next = n; } } public MyLinkedList() { clear(); } public void clear() { beginMarker = new Node (null, null, null); endMarker = new Node (null, beginMarker, null); beginMarker.next = endMarker; theSize = 0; modCount++; } public int size() { return theSize; } public boolean isEmpty() { return size() == 0; } public boolean add(AnyType x) { add(size(), x); return true; } public void add(int idx, AnyType x) { addBefore(getNode(idx), x); } public AnyType get(int idx) { return getNode(idx).data; } public AnyType set(int idx, AnyType newVal) { Node p = getNode(idx); AnyType oldVal = p.data; p.data = newVal; return oldVal; } public AnyType remove(int idx) { return remove(getNode(idx)); } private AnyType remove(Node p) { p.next.prev = p.prev; p.prev.next = p.next; theSize --; modCount ++; return p.data; } private Node getNode(int idx) { Node p; if(idx < 0 || idx > size()) { throw new IndexOutOfBoundsException(); } if(idx < size() / 2) { p = beginMarker.next; for (int i=0; i idx; i++) { p = p.prev; } } return p; } private void addBefore(Node p, AnyType x) { Node newNode = new Node (x, p.prev, p); newNode.prev.next = newNode; p.prev = newNode; theSize++; modCount++; } @Override public Iterator iterator() { return new LinkedListIterator(); } private class LinkedListIterator implements java.util.Iterator { private Node current = beginMarker.next; private int expectedModCount = modCount; private boolean okToRemove = false; public boolean hasNext() { return current != endMarker; } public AnyType next() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (!hasNext()) throw new NoSuchElementException(); AnyType nextItem = current.data; current = current.next; okToRemove = true; return nextItem; } public void remove() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (!okToRemove) throw new IllegalStateException(); MyLinkedList.this.remove(current.prev); okToRemove = false; expectedModCount ++; } } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/67381.html
摘要:結(jié)構(gòu)體是基于索引的數(shù)據(jù)結(jié)構(gòu),它提供了對(duì)其元素的隨機(jī)訪(fǎng)問(wèn),其性能為。在這樣情況下,其元素搜索的復(fù)發(fā)度為。此外,還有方便的方法和返回。隊(duì)列操作接口提供類(lèi)似隊(duì)列的行為實(shí)際上擴(kuò)展了接口這些方法檢索第一個(gè)元素并將其從列表中刪除。結(jié)論通常是默認(rèn)的實(shí)現(xiàn)。 1. 介紹 LinkedList是一個(gè)雙向鏈表, 實(shí)現(xiàn)了List和Deque接口。它實(shí)現(xiàn)所有可選的list操作,并且存儲(chǔ)對(duì)象可以為null。 2....
摘要:什么是是一個(gè)雙向連表,實(shí)現(xiàn)了接口,該接口中定義了雙向連表的一般操作。也實(shí)現(xiàn)了接口,所以包含的基本方法新增,刪除,插入等都實(shí)現(xiàn)了。也繼承了該類(lèi)中定義了順序訪(fǎng)問(wèn)所需實(shí)現(xiàn)的方法。 什么是LinkedList 1 LinkedList 是一個(gè) Doubly-linked list雙向連表,實(shí)現(xiàn)了Deque接口,該接口中定義了雙向連表的一般操作。 2 LinkedList 也實(shí)現(xiàn)了List接...
摘要:相關(guān)庫(kù)編程思路方法用于將元素追加到鏈表尾部,借由方法來(lái)實(shí)現(xiàn)注意各個(gè)函數(shù)的邊界條件處理。自己的實(shí)現(xiàn)源代碼地址 起因 最近在看《數(shù)據(jù)結(jié)構(gòu)與算法--javascript描述》,然后上npmjs.org去搜索,想找合適的庫(kù)參考并記錄下來(lái),以備以后用時(shí)能拿來(lái)即用,最沒(méi)有發(fā)現(xiàn)很合自己意的,于是就決定自己一一實(shí)現(xiàn)出來(lái)。 npmjs相關(guān)庫(kù) complex-list、smart-list、singly-...
摘要:在閱讀源碼之前,我們先對(duì)的整體實(shí)現(xiàn)進(jìn)行大致說(shuō)明實(shí)際上是通過(guò)雙向鏈表去實(shí)現(xiàn)的。獲取的最后一個(gè)元素由于是雙向鏈表而表頭不包含數(shù)據(jù)。實(shí)際上是判斷雙向鏈表的當(dāng)前節(jié)點(diǎn)是否達(dá)到開(kāi)頭反向迭代器獲取下一個(gè)元素。 第1部分 LinkedList介紹 LinkedList簡(jiǎn)介 LinkedList 是一個(gè)繼承于A(yíng)bstractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操...
摘要:提供了順序訪(fǎng)問(wèn)的方法,當(dāng)然,大部分方法都依賴(lài)于來(lái)實(shí)現(xiàn),所以將鍋甩給了子類(lèi)。實(shí)現(xiàn)了自己的遍歷方法利用了鏈表結(jié)構(gòu)的特性,進(jìn)行遍歷。其中有如下屬性記錄遍歷狀態(tài)。該方法位于中到數(shù)組中這里返回的不是,其實(shí)是 java.util.LinkedList Java中有現(xiàn)成的隊(duì)列可以用嗎 有,就是LinkedList。LinkedList實(shí)現(xiàn)的接口如下,其實(shí)也可以當(dāng)做stack使用: public cl...
閱讀 688·2021-11-18 10:07
閱讀 2878·2021-09-22 16:04
閱讀 873·2021-08-16 10:50
閱讀 3326·2019-08-30 15:56
閱讀 1784·2019-08-29 13:22
閱讀 2648·2019-08-26 17:15
閱讀 1229·2019-08-26 10:57
閱讀 1103·2019-08-23 15:23