LinkedList的理解和代码自己实现

川长思鸟来 2022-05-17 04:28 160阅读 0赞

在实现LinkedList的时候主要考虑三个类：

1.MyLinkedList类本身，它包含了两端的链、标的大小以及一些方法，在链的两端加了两个额外的节点，头结点(header node)和尾节点(tail node)用来标示链头和链尾。

2.Node类，它可能是一个私有的嵌套类。一个节点包含数据以及前一个节点的连接和道下一个节点的连接，还有一个构造方法。

3.LinkedListIterator类，该类抽象了位置的概念，是一个私有类，并实现接口Iterator。提供了hasNext()、next()和remove()方法。

具体的看下面的代码：

import java.util.ConcurrentModificationException;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    /**
     * @author QuLei
     *
     * @param <AnyType>泛型表示任意的类型均可以放入容器内
     * 自己实现LinkedList
     */
    public class MyLinkedList<AnyType> implements Iterable<AnyType> {
    	private int theSize;
    	private int modCount;
    	//创建两个额外的节点一个作为头结点，一个作为尾节点
    	private Node<AnyType> beginMarker;
    	private Node<AnyType> endMarker;
    	
    	/**
    	 * @author QuLei
    	 *
    	 * @param <AnyType>
    	 * 定义一个节点，表示链表的存储结构
    	 */
    	private static class Node<AnyType>{
    		public AnyType data;
    		public Node<AnyType> prev;
    		public Node<AnyType> next;
    		public Node(AnyType data, Node<AnyType> prev, Node<AnyType> next) {
    			super();
    			this.data = data;
    			this.prev = prev;
    			this.next = next;
    		}
    	}
    	
    	
    	
    
    	public MyLinkedList() {
    		clear();
    	}
    	
    	/**
    	 * change the size of the collection to zero
    	 */
    	public void clear() {
    		beginMarker = new Node<AnyType>(null, null, null);
    		endMarker = new Node<AnyType>(null, beginMarker, null);
    		beginMarker.next = endMarker;
    		theSize = 0 ;
    		modCount ++;
    		
    	}
    
    	public int size() {
    		return theSize;
    	}
    
    	public boolean isEmpty() {
    		return size() == 0;
    	}
    	/**调用此方法就是直接在尾部添加
    	 * @param x 要添加的元素
    	 * @return 成功返回true,若失败会抛异常出去
    	 */
    	public boolean add(AnyType x) {
    		add(size(),x);
    		return true;
    	}
    	/**
    	 * @param idx
    	 * @param x
    	 */
    	public void add(int idx,AnyType x) {
    		addBefore(getNode(idx),x);
    	}
    	
    	/**修改指定位置的值
    	 * @param idx
    	 * @param newVal
    	 * @return
    	 */
    	public AnyType set(int idx,AnyType newVal) {
    		Node<AnyType> p = getNode(idx);
    		AnyType oldVal = p.data;
    		p.data = newVal;
    		return oldVal;
    	}
    	
    	/**删除指定位置的元素
    	 * @param idx
    	 * @return
    	 */
    	public AnyType remove(int idx) {
    		return remove(getNode(idx));
    	}
    	/**查询指定位置的值
    	 * @param idx
    	 * @return
    	 */
    	public AnyType get(int idx) {
    		return getNode(idx).data;
    	}
    	
    	/**判断是否包含某个元素
    	 * @param x  要判断的元素
    	 * @return  返回是否包含该元素
    	 */
    	public boolean contains(AnyType x) {
    		Node<AnyType> p = beginMarker.next;
    		while(p != endMarker && !(p.data.equals(x))) {
    			p = p.next;
    		}
    		return (p != endMarker);
    	}
    	/**在给定节点前面插入元素
    	 * @param p
    	 * @param x
    	 */
    	private void addBefore(Node<AnyType> p,AnyType x) {
    		Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p);
    		//newNode.prev = p.prev;   这两句代码可以直接放入构造器中
    		//newNode.next = p;
    		p.prev = p.prev.next = newNode; //把原来链中的结构链接上
    		theSize ++;
    		modCount ++;
    	}
    	private AnyType remove(Node<AnyType> p) {
    		p.prev.next = p.next;
    		p.next.prev = p.prev;
    		theSize --;
    		modCount ++;
    		return p.data;
    	}
    	/**获取指定位置的节点
    	 * @param idx  :指定的位置
    	 * @return  ：返回该指定位置处的节点
    	 */
    	private Node<AnyType> getNode(int idx){
    		Node<AnyType> p;
    		if(idx < 0 || idx > size()) {
    			throw new IndexOutOfBoundsException();
    		}
    		if(idx < size()/2) {
    			p = beginMarker;
    			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;
    	}
    	@Override
    	public Iterator<AnyType> iterator() {
    		// TODO Auto-generated method stub
    		return new LinkedListIterator();
    	}
    	
    	private class LinkedListIterator implements Iterator<AnyType>{
    		//起始位置为第一个节点
    		private Node<AnyType> current = beginMarker.next;
    		private int exceptedModCount = modCount;
    		private boolean okToRemove = false;
    		@Override
    		public boolean hasNext() {
    			// TODO Auto-generated method stub
    			return current != endMarker; 
    		}
    
    		@Override
    		public AnyType next() {
    			// TODO Auto-generated method stub
    			if(modCount != exceptedModCount) {
    				throw new ConcurrentModificationException();
    			}
    			if(!hasNext()) {
    				throw new NoSuchElementException();
    			}
    			AnyType nextItem = current.data;
    			current = current.next;
    			okToRemove = true;
    			return nextItem;
    		}
    		
    		public void remove() {
    			if(modCount != exceptedModCount) {
    				throw new ConcurrentModificationException();
    			}
    			if(!okToRemove) {
    				throw new IllegalStateException();
    			}
    			MyLinkedList.this.remove(current.prev);
    			okToRemove = false;
    			exceptedModCount ++;
    		}
    	}
    
    }