[数据结构]双链表实现 LinkedList

末蓝、 2023-03-03 06:30 111阅读 0赞

I'm Shendi,最近在整数据结构

下面是我练习的一个双链表

/**
     * 手写的LinkedList,实现List,双链表.<br>
     * 内部类 Node,代表一个结点.
     * @author Shendi <a href='tencent://AddContact/?fromId=45&fromSubId=1&subcmd=all&uin=1711680493'>QQ</a>
     * @version 1.0
     */
    public class LinkedList<E> implements Iterable<E> {
    	
    	private Node<E> first;
    	private Node<E> last;
    	
    	private int size;
    	
    	private static class Node<E> {
    		Node<E> prev;
    		E data;
    		Node<E> next;
    		public Node (Node<E> prev, E data, Node<E> next) {
    			this.prev = prev;
    			this.data = data;
    			this.next = next;
    		}
    	}
    	
    	/**
    	 * 添加操作,如果第一个结点为空则直接将结点添加为第一个结点,最后一个结点也为第一个结点.<br>
    	 * 不为空则直接将结点添加到最后一个结点的后面.
    	 * @author Shendi <a href='tencent://AddContact/?fromId=45&fromSubId=1&subcmd=all&uin=1711680493'>QQ</a>
    	 * @param obj 要添加的元素
    	 */
    	public void add(E obj) {
    		if (first == null) {
    			first = new Node<E>(null, obj, null);
    			last = first;
    		} else {
    			last.next = new Node<E>(last, obj, null);
    			last = last.next;
    		}
    		size++;
    	}
    	
    	/**
    	 * 获取操作,二分获取.
    	 * @author Shendi <a href='tencent://AddContact/?fromId=45&fromSubId=1&subcmd=all&uin=1711680493'>QQ</a>
    	 * @param index 指定元素下标
    	 * @return 获取的元素
    	 */
    	public E get(int index) {
    		if (index >= size) return null;
    		if (index < (size >> 1)) {
    			Node<E> node = first;
    			for (int i = 1;i < index;i++) {
    				if (node == null) return null;
    				node = node.next;
    			}
    			return node.data;
    		} else {
    			Node<E> node = last;
    			for (int i = size - 1;i > index;i--) {
    				if (node == null) return null;
    				node = node.prev;
    			}
    			return node.data;
    		}
    	}
    	
    	/**
    	 * 删除操作,将结点的上一个结点的next指向要删除结点的next.<br>
    	 * 如果结点是第一个则为直接将第一个结点为要删除结点的下一个结点.<br>
    	 * 如果结点是最后一个则为将最后一个结点为要删除节点的上一个结点.
    	 * @author Shendi <a href='tencent://AddContact/?fromId=45&fromSubId=1&subcmd=all&uin=1711680493'>QQ</a>
    	 * @param o 要删除的元素
    	 * @return 被删除的元素 null则代表删除失败.
    	 */
    	public E remove(Object o) {
    		if (o == null) {
    			for (Node<E> node = first;node != null;node = node.next) {
    				if (node.data == null) {
    					if (node == first) {
    						first = node.next;
    						last = null;
    					} else {
    						if (node == last) {
    							last = node.prev;
    							last.next = null;
    						}
    						node.prev.next = node.next;
    					}
    					size--;
    					return node == null ? null : node.data;
    				}
    			}
    		} else {
    			for (Node<E> node = first;node != null;node = node.next) {
    				if (o.equals(node.data)) {
    					if (node == first) {
    						first = node.next;
    						last = null;
    					} else {
    						if (node == last) {
    							last = node.prev;
    							last.next = null;
    						}
    						node.prev.next = node.next;
    					}
    					size--;
    					return node == null ? null : node.data;
    				}
    			}
    		}
    		return null;
    	}
    	
    	public int size() { return size; }
    	
    
    	@Override
    	public Iterator<E> iterator() {
    		it.node = first;
    		return it;
    	}
    	
    	private LinkedIterator it = new LinkedIterator();
    	private class LinkedIterator implements Iterator<E> {
    
    		Node<E> node;
    		
    		@Override
    		public boolean hasNext() {
    			return node == null ? false : node.data != null;
    		}
    
    		@Override
    		public E next() {
    			E data = node.data;
    			node = node.next;
    			return data;
    		}
    		
    	}
    	
    	public static void main(String[] args) {
    		LinkedList<String> list = new LinkedList<>();
    		ArrayList<Integer> lis1 = new ArrayList<Integer>();
    		lis1.toArray();
    		list.add("hello");
    		list.add("world");
    //		list.remove("world");
    		list.add(".");
    		
    //		for (int i = 0;i < list.size();i++) {
    //			System.out.println(list.get(i));
    //		}
    		for (String str : list) System.out.println(str);
    	}
    	
    }