手写LinkedList集合

喜欢ヅ旅行 2022-03-20 15:46 249阅读 0赞

### 1.实现源码 ###

package com.weichai.linkedlist;
    
    import java.util.LinkedList;
    
    /**
        *    手写LinkeList
        *    底层实现是一个双向链表
     * @author linhaiy
     * @date 2019.02.12
     * @param <E>
     */
    public class ExtLinkedList<E> {
    
    	class Node {
    		Node prev;           // 上一个节点
    		Object object;       // 节点内容
    		Node next;           // 下一个节点
    	}
    	
    	private Node first;    // 第一个元素
    	private Node last;     // 最后一个元素
    	private int size;      // 实际存放在长度
    	
    	/**
    	    *    添加新的节点元素内容
    	 * @param e
    	 */
    	public void add(E e) {
    		Node node = new Node();
    		node.object = e;
    		if(first == null) {
    			first = node;         // 第一个元素和最后一个元素都是为node
    		}else {
    			node.prev = last;     // 存放上一个节点内容
    			last.next = node;     // 设置上一个节点的next为当前节点
    		}
    		last = node;
    		size ++;
    	}
    	
    	/**
    	    * 在节点index位置添加节点Node元素
    	 * @param index
    	 * @param e
    	 */
    	public void add(int index, E e) {
    		// 1.循环遍历到当前index位置Node
    		// 2.新增当前节点
    		Node newNode = new Node();
    		newNode.object = e;
    		// 3.获取原来的节点
    		ExtLinkedList<E>.Node oldNode = getNode(index);      // 获取原来的节点
    		ExtLinkedList<E>.Node olNodePrev = oldNode.prev;     // 获取原来上一个节点
    		
    		// 4.新增节点的上一个还是当前Node节点的 上一个节点,下一个就是原来的节点
    		// 原来上一个节点变为当前节点
    		oldNode.prev = newNode;
    		if(oldNode == null) {
    			first = newNode;
    		}else {
    			olNodePrev.next = newNode;    // 原来上一个节点的下一个节点变为当前节点
    		}
    		newNode.next = oldNode;           // 新节点的下一个节点为原来节点
    		size ++;
    	}
    	
    	/**
    	    *    获取节点某个位置的元素
    	 * @param index
    	 * @return
    	 */
    	public E get(int index) {
    		Node node = getNode(index);
    		return (E) node.object;
    	}
    
    	/**
    	    *   获取节点Node某个位置的元素
    	 * @param index
    	 * @return
    	 */
    	public Node getNode(int index) {
    		// TODO Auto-generated method stub
    		Node node = null;
    		if(first !=null) {
    			node = first;
    			for (int i = 0; i < index; i++) {
    				node = node.next;
    			}
    		}
    		return node;
    	}
    	
    	/**
    	    *   移出节点某个位置的元素
    	 * @param index
    	 */
    	public void remove(int index) {
    		checkElementIndex(index);
    		Node node = getNode(index);
    		if(node != null) {
    			Node prevNode = node.prev;
    			Node nextNode = node.next;
    			if (prevNode != null) {       // 设置上一个节点的next为当前删除节点的next
    				prevNode.next = nextNode;
    			}
    			
    			// 判断是否是最后一个节点
    			if (nextNode != null) {
    				nextNode.prev = prevNode;
    			}
    		}
    		size --;
    	}
    	
    	/**
    	    *   判断当前位置是否在节点范围内
    	 * @param index
    	 * @return
    	 */
    	private boolean isElementIndex(int index) {
    		return index >= 0 && index < size;
    	}
    	
    	/**
    	    *    判断节点当前位置是否合法
    	 * @param index
    	 */
    	private void checkElementIndex(int index) {
    		if (!isElementIndex(index))
    			throw new IndexOutOfBoundsException("越界啦!");
    	}
    	
    	public static void main(String[] args) {
    		ExtLinkedList<String> linkeList = new ExtLinkedList<String>();
    		linkeList.add("A");
    		linkeList.add("B");
    		linkeList.add("C");
    		linkeList.add("D");
    		linkeList.add(2, "E");
    		for (int i = 0; i < linkeList.size; i++) {
    			System.out.println(linkeList.get(i));
    		}
    		
    //		LinkedList<String> list = new LinkedList<String>();
    	}
    }