网站建站网站开发,什么网站可以做投资,内蒙古住房与城乡建设厅网站网址,怎样做学校网站LinkedList就传说中的双向链表了。是List 接口的链接列表实现。实现所有可选的列表操作#xff0c;并且允许所有元素#xff08;包括 null#xff09;。除了实现 List 接口外#xff0c;LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方… LinkedList就传说中的双向链表了。是List 接口的链接列表实现。实现所有可选的列表操作并且允许所有元素包括 null。除了实现 List 接口外LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
查看LinkedList的构造函数/*** Constructs an empty list.*/public LinkedList() {header.next header.previous header;
} 这里的header变量的定义如下 private transient EntryE header new EntryE(null, null, null); 表示双向循环链表的头结点。其中的Entry定义了双向链表的结构 private static class EntryE {E element;EntryE next;EntryE previous;Entry(E element, EntryE next, EntryE previous) {this.element element;this.next next;this.previous previous;}
} Entry中包括数据元素、前续结点和后续结点。 构造函数即是初始化一个只包含header头结点一个元素的双向链表。
可以得出LinkedList实质上就是一个双向链表并把header作为头结点。查看LinkedList的add(E)方法public boolean add(E e) {addBefore(e, header);return true;
} add(E)方法主要指向了addBefore(E, Entry)函数 private EntryE addBefore(E e, EntryE entry) {EntryE newEntry new EntryE(e, entry, entry.previous);newEntry.previous.next newEntry;newEntry.next.previous newEntry;size;modCount;return newEntry;
} 这个方法中传入的第二个参数entry为header头结点表示把元素插入到header头结点之前。然后后两句分别表示设置前续结点的后续结点和后续结点的前续结点。以便连接成双向链表。
可以得出LinkedList的add(E)方法把新结点插入到header头结点之前即列表的结尾。查看LinkedList的set(int, E)方法/*** 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) {EntryE e entry(index);E oldVal e.element;e.element element;return oldVal;
} 这个函数主要是设置某个索引位置的结点。首先调用了entry(int)方法 /*** Returns the indexed entry.*/private EntryE entry(int index) {if (index 0 || index size)throw new IndexOutOfBoundsException(Index: index, Size: size);EntryE e header;if (index (size 1)) {for (int i 0; i index; i)e e.next;} else {for (int i size; i index; i--)e e.previous;}return e;
} 这里首先判断需要设置的位置是否越界如果越界则抛出异常。然后通过循环找到需要替换的结点。 接下来回到set(int ,E)函数把旧的结点替换成新的结点并返回旧的结点。
可以得出set(int ,E)方法需要循环遍历链表时间开销比较大。查看LinkedList的push(E)方法/*** Pushes an element onto the stack represented by this list. In other* words, inserts the element at the front of this list.** pThis method is equivalent to {link #addFirst}.** param e the element to push* since 1.6*/public void push(E e) {addFirst(e);
} push(E)方法主要调用了addFirst(E)方法 /*** Inserts the specified element at the beginning of this list.** param e the element to add*/public void addFirst(E e) {addBefore(e, header.next);
} 这里继续调用addBefore(E, Entity)表示把新节点插入到header头结点之后。
可以得出push(E)方法主要是把新节点插入到header头结点之后。查看LinkedList的pop()方法/*** Pops an element from the stack represented by this list. In other* words, removes and returns the first element of this list.** pThis method is equivalent to {link #removeFirst()}.** return the element at the front of this list (which is the top* of the stack represented by this list)* throws NoSuchElementException if this list is empty* since 1.6*/public E pop() {return removeFirst();
} 这里继续调用了removeFirst()方法 /*** 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() {return remove(header.next);
} 这里继续调用remove(EntryE)方法 /*** Retrieves and removes the head (first element) of this list.** return the head of this list* throws NoSuchElementException if this list is empty* since 1.5*/private E remove(EntryE e) {if (e header)throw new NoSuchElementException();E result e.element;e.previous.next e.next;e.next.previous e.previous;e.next e.previous null;e.element null;size--;modCount;return result;
} 在调用remove(EntryE)方法时传入了header的下一个结点。如果传入的下一个结点是header的话表示此事链表中只有一个结点header此时抛出异常。如果找到则删除该节点注意这里双向链表删除结点时的步骤并返回被删除的结点。
可以得出pop()方法删除的是header头结点之后的结点并返回被删除的结点。★ LinkedList实质上就是一个双向链表并把header作为头结点。 ★ LinkedList的add(E)方法把新结点插入到header头结点之前。 ★ set(int ,E)方法需要循环遍历链表时间开销比较大。 ★ push(E)方法主要是把新节点插入到header结点之前 ★ pop()方法删除的是header头结点之后的结点并返回被删除的结点。
