Java之双向链表,自定义LinkedList

浅浅的花香味﹌ 2022-05-10 08:26 208阅读 0赞

> 这个是很久之前完成的,用作Demo，先上结构图

![70][] 话不多少,上代码

package cn.marding.App;
    
    public class MyLinkedList implements MyList {
    	// 表示集合的第一个元素所在的节点
    	private Node first;
    	// 表示集合中的最后一个元素所在的节点
    	private Node last;
    
    	private int size;
    
    	public MyLinkedList() {
    	}
    
    	@Override
    	public void add(Object obj) {
    		linkLast(obj);
    		size++;
    	}
    
    	@Override
    	public void add(int index, Object obj) {
    		// 可以等于size，如果等于size，则将元素加到最后
    		if (index < 0 || index > size) {
    			throw new IllegalArgumentException();
    		}
    
    		if (index == size)
    			linkLast(obj);
    		else
    			linkBefore(obj, node(index));
    
    		size++;
    	}
    
    	/**
    	 * 将元素增加到指定节点处
    	 * 
    	 * @param obj
    	 * @param node
    	 */
    	private void linkBefore(Object obj, Node node) {
    		Node temp = new Node(null, obj, node);
    
    		Node up = node.prev;
    		if (up != null) {
    			up.next = temp;
    			temp.prev = up;
    			node.prev = temp;
    		} else {
    			first = temp;
    		}
    
    	}
    
    	/**
    	 * 将元素添加到链表的最后
    	 * 
    	 * @param obj
    	 */
    	private void linkLast(Object obj) {
    		Node temp = new Node(last, obj, null);
    
    		if (first == null)
    			first = last = temp;
    		else {
    			last.next = temp;
    			last = temp;
    		}
    
    	}
    
    	/**
    	 * 返回指定索引处的节点
    	 * 
    	 * @param index
    	 * @return
    	 */
    	private Node node(int index) {
    		Node node = first;
    		if (node != null) {
    			for (int i = 0; i < index; i++) {
    				node = node.next;
    			}
    		}
    		return node;
    	}
    
    	@Override
    	public void remove(Object obj) {
    		int index = 0;
    		for (Node temp = first; temp != null;) {
    			if (temp.obj.equals(obj)) {
    				temp = temp.next;
    				remove(index);
    			} else {
    				temp = temp.next;
    				index++;
    			}
    		}
    	}
    
    	@Override
    	public void remove(int index) {
    		rangCheck(index);
    		// 获得索引为index的节点
    		Node temp = node(index);
    
    		// 获得改节点的上一个节点和下一个节点
    		Node up = temp.prev;
    		Node down = temp.next;
    
    		// 如果删除的是第一个节点
    		if (up == null) {
    			down.prev = null;
    			first = down;
    			size--;
    			return;
    		}
    
    		// 如果删除的是最后一个节点
    		if (down == null) {
    			up.next = null;
    			last = up;
    			size--;
    			return;
    		}
    		// 重新设置连接关系
    		up.next = down;
    		down.prev = up;
    
    		size--;
    	}
    
    	@Override
    	public Object get(int index) {
    		rangCheck(index);
    		Node temp = node(index);
    		return temp == null ? null : temp.obj;
    	}
    
    	/**
    	 * 判断索引是否合法
    	 * 
    	 * @param index
    	 */
    	private void rangCheck(int index) {
    		if (index < 0 || index >= size) {
    			throw new IllegalArgumentException();
    		}
    	}
    
    	@Override
    	public void set(int index, Object obj) {
    		rangCheck(index);
    		Node temp = node(index);
    		temp.obj = obj;
    	}
    
    	@Override
    	public int indexOf(Object obj) {
    		// 用来记录索引
    		int index = 0;
    
    		for (Node temp = first; temp != null;) {
    			if (temp.obj.equals(obj)) {
    				return index;
    			}
    			temp = temp.next;
    			index++;
    		}
    		// 集合中不存在该对象，就返回-1
    		return -1;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		return first == null ? true : false;
    	}
    
    	@Override
    	public void clear() {
    		for (Node temp = first; temp != null;) {
    			Node next = temp.next;
    
    			temp.prev = null;
    			temp.obj = null;
    			temp.next = null;
    
    			temp = next;
    		}
    
    		size = 0;
    		first = last = null;
    	}
    
    	@Override
    	public int size() {
    		return size;
    	}
    
    	/**
    	 * 用来存储元素，同时也是存储了每个元素的相邻元素的信息
    	 * 
    	 * @author 
    	 * 
    	 */
    	private class Node {
    		// 上一个节点
    		Node prev;
    		// 本节点中存储的对象
    		Object obj;
    		// 下一个节点
    		Node next;
    
    		Node(Node prev, Object obj, Node next) {
    			this.prev = prev;
    			this.obj = obj;
    			this.next = next;
    		}
    	}
    
    }

> PS,上面还有一个接口,方法都被Override了,大家自行补充

[70]: /images/20220510/4edf43fed1ac40719fb32fdf2f6e552c.png