java自定义双向链表

  今天学习了链表的相关知识，并在此基础上写了一个自定义的双向结点类和链表类。
  链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的结点之间的引用链接实现的。相比于线性表顺序结构，链表比较方便插入和删除操作。
  数组在定义时是在内存中开辟连续的一块区域，而链表则是不固定的，所以在访问时数组更加高效。但是数组必须在定义时就指定大小，所以很有可能造成内存的浪费。还有数组只需要在栈中分配空间，方便快捷。而链表还需要使用到堆中的空间。
下面是自定义的双向结点类

public class LLNode {

	private Object obj;
	private LLNode child = null;
	private LLNode parent = null;

	/**
	 * 它的构造方法
	 */
	public LLNode(Object obj) {
		this.obj = obj;
	}

	public LLNode getChild() {
		return child;
	}

	public void setChild(LLNode child) {
		this.child = child;
	}

	public LLNode getParent() {
		return parent;
	}

	public void setParent(LLNode parent) {
		this.parent = parent;
	}

	public Object getObj() {
		return obj;
	}

}

下面是自定义的双向链表类

public class LinkList {

	private static LLNode head = null;
	private LLNode tail = null;


	/**
	 * 双向链表的构造方法
	 */
	public LinkList() {

	}

	/**
	 * 重写构造方法，创建链表时传入根结点
	 */
	public LinkList(Object obj) {
		head = new LLNode(obj);
		tail = head;
	}

	/**
	 * 向链表最后添加元素
	 * 
	 * @param obj
	 *            添加的元素
	 */
	public void add(Object obj) {
		LLNode node = new LLNode(obj);
		if (head == null) {
			head = new LLNode(obj);
			tail = head;
		} else {
			tail.setChild(node);
			node.setParent(tail);
			tail = node;
		}
	}

	/**
	 * 重写添加的方法 在指定位置添加
	 * 
	 * @param obj
	 *            添加的元素
	 * @param index
	 *            添加的位置(下标值)
	 */
	public void add(Object obj, int index) {
		LLNode node = new LLNode(obj);
		if (index < 0 || index > size()) {// 如果越界
			throw new RuntimeException("越界！可添加的范围为：0~" + size() + ".");
		} else if (head == null) {// 如果没有开始结点
			head = node;
			tail = head;
		} else if (index == 0) {// 如果插入到链表开头
			node.setChild(head);
			head.setParent(node);
			head = node;
		} else if (index == size()) {// 如果插入到链表结尾
			add(obj);
		} else {
			int i = 0;
			LLNode current = head;
			// 找到位置
			while (i != index) {
				current = current.getChild();
				i++;
			}
			LLNode fNode = current.getParent();
			fNode.setChild(node);
			node.setParent(fNode);
			node.setChild(current);
			current.setParent(node);
		}

	}
	
	/**
	 * 替换指定下标处得元素
	 * @param obj 给予替换的元素
	 * @param index  指定的下标
	 */
	public void set(Object obj, int index){
		LLNode node = new LLNode(obj);
		if (index < 0 || index > size()) {// 如果越界
			throw new RuntimeException("越界！可添加的范围为：0~" + size() + ".");
		} else if (head == null) {// 如果没有开始结点
			System.out.println("没有可以替换的位置，因为它是空链表！");
		} else if (index == 0) {// 如果替换到链表开头
			node.setChild(head.getChild());
			head.getChild().setParent(node);
			head = node;
		} else if (index == size()) {// 如果替换到链表结尾
			node.setParent(tail.getParent());
			tail.getParent().setChild(node);
			tail = node;
		} else {
			int i = 0;
			LLNode current = head;
			// 找到位置
			while (i != index) {
				current = current.getChild();
				i++;
			}
			LLNode pNode = current.getParent();
			LLNode cNode = current.getChild();
			pNode.setChild(node);
			node.setParent(pNode);
			node.setChild(cNode);
			cNode.setParent(node);
		}

	}
	
	/**
	 * 返回此链表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1
	 * @param obj  指定的元素
	 * @return 返回此列表中首次出现的指定元素的下标值
	 */
	public int indexOf(Object obj){
		LLNode current = head;
			// 找到位置
			int i;
			for(i = 0;i<size();i++){
				if(current.getObj() == obj){
					break;
				}
				if(i==(size()-1)){
					return -1;
				}
				current = current.getChild();
			}
			return i;
	}

	/**
	 * 移除链表中的一个结点
	 * 
	 * @param obj
	 *            移除此元素的节点
	 * @return 返回表示是否移除
	 */
	public boolean remove(Object obj) {
		LLNode current;
		if (head.getObj() == obj) {
			current = head.getChild();
			current.setParent(null);
			head = current;
			return true;
		} else if (tail.getObj() == obj) {
			current = tail.getParent();
			current.setChild(null);
			tail = current;
			return true;
		} else {
			current = head.getChild();
			// 找到位置
			for(int i = 0;i<size();i++){
				if(current.getObj() == obj){
					break;
				}
				if(i==(size()-1)){
					return false;
				}
				current = current.getChild();
			}
			LLNode cnode = current.getChild();
			LLNode pnode = current.getParent();
			pnode.setChild(cnode);
			cnode.setParent(pnode);
			return true;
		}
	}

	/**
	 * 移除链表中的一个元素，并返回它
	 * 
	 * @param index
	 *            指定的下标位置
	 * @return 返回这个指定位置的元素
	 */
	public Object remove(int index) {
		LLNode current ;
		if(size() == 0){
			System.out.println("链表中没有元素，无法移除！");
			return null;
		}else if (index < 0 || index > size()) {// 如果越界
			throw new RuntimeException("越界！可移除的范围为：0~" + size() + ".");
		}else if(index == 0){//如果指定位置在开头
			LLNode temp = head;
			current = head.getChild();
			current.setParent(null);
			head = current;
			return temp.getObj();
		}else if(index == size()){//如果指定位置在结尾
			LLNode temp = tail;
			current = tail.getParent();
			current.setChild(null);
			tail = current;
			return temp.getObj();
		}else{
			current = head;
			int i=0;
			while(i != index){
				i++;
				current = current.getChild();
			}
			LLNode cnode = current.getChild();
			LLNode pnode = current.getParent();
			pnode.setChild(cnode);
			cnode.setParent(pnode);
			return current.getObj();
		}
	}

	/**
	 * 移除链表中所有元素
	 */
	public void removeall() {
		head.setChild(null);
		tail.setParent(null);
		head = null;
		tail = head;
	}

	/**
	 * 判断链表长度的方法
	 * 
	 * @return 返回链表的长度
	 */
	public int size() {
		int i = 0;
		LLNode current = head;
		while (current != null) {
			current = current.getChild();
			i++;
		}
		return i;
	}
	
	/**
	 * 得到指定下标的元素，但不在链表中移除它
	 * @param index 指定的下标位置
	 * @return 返回该元素
	 */
	public Object get(int index){
		if(size() == 0){
			System.out.println("链表中没有元素，无法得到！");
			return null;
		}else if (index < 0 || index > size()) {// 如果越界
			throw new RuntimeException("越界！可得到的范围为：0~" + size() + ".");
		}else{
			LLNode current = head;
			int i=0;
			while(i != index){
				i++;
				current = current.getChild();
			}
			return current.getObj();
		}
		
	}

	/**
	 * 从此结点向下遍历的方法
	 * 
	 * @param node
	 *            给予的起始结点
	 */
	public void printfromHead(LLNode node) {
		if (node == null) {
			System.out.println("链表为空！");
		} else {
			System.out.println(node.getObj());
			if (node.getChild() != null) {
				LLNode current = node.getChild();
				printfromHead(current);
			}
		}
	}

	/**
	 * 从此结点向上遍历的方法
	 * 
	 * @param node
	 *            给予的起始结点
	 */
	public void printfromTail(LLNode node) {
		if (node == null) {
			System.out.println("链表为空！");
		} else {
			System.out.println(node.getObj());
			if (node.getParent() != null) {
				LLNode current = node.getParent();
				printfromTail(current);
			}
		}
	}

	/**
	 * 遍历打印链表的方法
	 * 
	 * @param node
	 *            给予的起始结点
	 */
	public void printList(LLNode node) {
		if (node == null) {
			System.out.println("链表为空！");
		} else {
			// 开始向上遍历
			if (node.getParent() != null) {
				System.out.println("----开始向上遍历----");
				LLNode current = node;
				printfromTail(current);
			} else {
				System.out.println("已是根节点，无法向上遍历");
			}
			// 开始向下遍历
			if (node.getChild() != null) {
				System.out.println("----开始向下遍历----");
				LLNode current = node;
				printfromHead(current);
			} else {
				System.out.println("已是尾节点，无法向下遍历");
			}
		}
	}
}