小伙伴们来自己实现LinkedList
继前面实现ArrayList后，今天和小伙伴一起实现LinkedList，LinkedList实现我们采用双向链表来实现，在每次查找时候，如果该查找元素位于该链表的前半段，则从开始检索，如果位于链表的后半段，则从尾部开始检索。以下先贴出代码：
package com.david.duan;import java.util.Iterator;public class MyLinkedList implements Iterable<Student>{//表示该链表的长度private int theSize;//每次链表被修改就增加此值private int modCount;//链表的头元素private Node<Student> beginMarker;//链表的尾元素private Node<Student> endMarker;//使用内部类来实现链表的每一个节点，每个节点有一个指向下一个元素的next，指向上一个元素的prev，以及自身的dataprivate static class Node<Student> {public Node(Student data, Node<Student> prev, Node<Student> next) {this.data = data;this.prev = prev;this.next = next;}public Student data;public Node<Student> prev;public Node<Student> next;}//链表的构造方法public MyLinkedList () {clear();}//清除链表，即使得链表的头元素指向链表的尾元素public void clear () {beginMarker = new Node<Student>(null, null, null);endMarker = new Node<Student>(null, beginMarker, null);beginMarker.next = endMarker;}//返回链表的长度public int size() {return theSize;}//判断链表是否为空public boolean isEmplty() {return size() == 0;}//向链表中添加元素public boolean add(Student x) {add(size(), x);return true;}public void add(int idx, Student x) {addBefore(getNode(idx), x);}//获取该节点的datapublic Student get(int idx) {return getNode(idx).data;}//设置该节点的值public Student set(int idx, Student newData) {Node<Student> oldNode = getNode(idx);Student oldData = oldNode.data;oldNode.data = newData;return oldData;}//删除该节点，并返回该节点的值public Student remove(int idx) {return remove(getNode(idx));}private Student remove(Node<Student> p) {p.prev.next = p.next;p.next.prev = p.prev;theSize--;modCount++;return p.data;}//执行添加private void addBefore (Node<Student> p, Student x) {Node<Student> newNode = new Node<Student>(x, p.prev, p);newNode.prev.next = newNode;p.prev = newNode;modCount++;}//查找节点private Node<Student> getNode(int idx) {Node<Student> 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.next;}}else {p = endMarker;for (int i = size();i>idx;i--) {p = p.prev;}}return p;}//此处类似于前面的ArrayList，用以保存并返回当前元素@Overridepublic Iterator<Student> iterator() {return new LinkedListIterator();}private class LinkedListIterator implements java.util.Iterator<Student> {private Node<Student> current = beginMarker.next;private int expectedModCount = modCount;private boolean okToRemove = false;@Overridepublic boolean hasNext() {return current != endMarker;}@Overridepublic Student next() {if (modCount != expectedModCount ) {throw new java.util.ConcurrentModificationException();}if(!hasNext()) {throw new java.util.NoSuchElementException();}Student nextData = current.data;current = current.next;okToRemove = true;return nextData;}@Overridepublic void remove() {if (modCount != expectedModCount ) {throw new java.util.ConcurrentModificationException();}if(!hasNext()) {throw new java.util.NoSuchElementException();}MyLinkedList.this.remove(current.prev);okToRemove = false;expectedModCount++;}}}