双向链表的实现

package cn.rjb;

public interface Position {
	public Object getElem();
	public Object setElem(Object e);
}

package cn.rjb;
/**
 * 双向链表节点
 * @author ljp
 *
 */
public class DLNode implements Position{
	//element表示节点的值
	private Object element;
	//prev代表上一节点
	private DLNode prev;
	//next代表下一个节点
	private DLNode next;

	public DLNode(){
		this(null,null,null);
	}

	public DLNode(Object e,DLNode p,DLNode n){
		element=e;
		prev=p;
		next=n;
	}

	public Object getElem(){
		return element;
	}

	public Object setElem(Object e){
		Object oldElem=element;
		element=e;
		return oldElem;
	}

	public DLNode getNext(){
		return next;
	}

	public DLNode getPrev(){
		return prev;
	}

	public void setNext(DLNode newNext){
		next=newNext;
	}

	public void setPrev(DLNode newPrev){
		prev=newPrev;
	}
}

package cn.rjb;
/**
 * 链表相关操作
 * @author ljp
 *
 */
public class DLList {

	//链表长度
	private static int length;
	//指向首节点
	private DLNode header;
	//指向尾节点
	private DLNode trailer;

	/**
	 * 构造函数，初始化链表
	 */
	public DLList(){
		header=new DLNode();
		trailer=new DLNode();
		header.setNext(trailer);
		trailer.setPrev(header);
		length=0;
	}

	/**
	 * 在链表的后面加上节点
	 * @param node
	 */
	public void addNode(Object element){
		addNode(element,length+1);
	}

	/**
	 * 在指定位置插入节点
	 * @param node
	 * @param pos
	 */
	public void addNode(Object element,int pos){
		int position=1;
		DLNode newNode=new DLNode();
		newNode.setElem(element);
		DLNode node=header.getNext();
		DLNode preNode=header.getNext();
		if(pos==1){
			newNode.setNext(node);
			newNode.setPrev(header);
			header.setNext(newNode);
			node.setPrev(newNode);
			length++;
		}else{
	    	if(pos>length+1||pos<1){
    			System.out.println("你插入的位置有误!"+length);
    		}else{
		    	while(position<pos){
	    			preNode=node;
	    			node=node.getNext();
	    			position++;
	    		}
	    		newNode.setNext(node);
	    		newNode.setPrev(preNode);
	    		preNode.setNext(newNode);
	    		node.setPrev(newNode);
	    		length++;
	    	}
		}
	}

	/**
	 * 删除指定位置的节点
	 * @param node
	 */
	public void removeNode(int pos){
		int position=1;
		DLNode node=header.getNext();
		DLNode preNode=header;
		while(position<pos){
			preNode=node;
			node=node.getNext();
			position++;
		}
		preNode.setNext(node.getNext());
		node.getNext().setPrev(preNode);
		length--;
	}

	/**
	 * 获取链表的长度
	 * @return
	 */
	public int getLength(){
		return length;
	}

	/**
	 * 取得指定位置的节点
	 * @param pos
	 * @return
	 */
	public DLNode getNode(int pos){
		int position=1;
		DLNode node=header.getNext();
		while(position<pos){
			node=node.getNext();
			position++;
		}
		return node;
	}

	/**
	 * 修改指定位置节点的元素值
	 * @param pos
	 * @param element
	 * @return
	 */
	public DLNode setNode(int pos,Object element){
		DLNode node=getNode(pos);
		node.setElem(element);
		return node;
	}

	/**
	 * 判断链表是否为空
	 * @return
	 */
	public boolean isEmpty(){
		return (0==length)?true:false;
	}

	/**
	 * 遍历链表
	 */
	public void Traversal(){
		DLNode node=header.getNext();
		while(node!=trailer){
			System.out.print(node.getElem());
			node=node.getNext();
			if(node!=trailer){
				System.out.print("->");
			}
		}
		System.out.println("");
	}
}

package cn.rjb;
/**
 * 双向链表测试类
 * @author ljp
 *
 */
import java.util.Scanner;
public class DLListTester {
	public static void main(String args[]){
		DLList list=new DLList();
		System.out.println("已有链表:");
		list.addNode(1);
		list.addNode(2);
		list.addNode(3);
		list.addNode(4);
		list.addNode(5);
		list.addNode(6);
		list.addNode(7);
		list.addNode(8);
		list.Traversal();
		Scanner s=new Scanner(System.in);
		while(true){
    		System.out.println("请输入你要执行的操作：1.增加   2.获得元素  3.删除  4.退出");
    		int select=s.nextInt();
	    	if(select==1){
    			System.out.println("输入你要插入的元素:");
	    		Integer newNum=s.nextInt();
	    		System.out.println("输入你要插入的位置，范围是1~"+(list.getLength()+1));
    			int position=s.nextInt();
    			while(position>(list.getLength()+1)||position<1){
    				System.out.println("您输入的位置不正确,请重新输入");
    				position=s.nextInt();
    			}
    			list.addNode(newNum,position);
	    		System.out.println("执行后的结果为：");
    			list.Traversal();
	    	}else if(select==2){
    			System.out.println("请输入你要查找的元素的位置,范围是1~"+list.getLength());
	    		int pos=s.nextInt();
    			while(pos>list.getLength()||pos<1){
    				System.out.println("您输入的位置不正确,请重新输入");
    				pos=s.nextInt();
    			}
	    		DLNode node=list.getNode(pos);
	    		System.out.println(pos+"号位置的元素值为："+(Integer)node.getElem());
    			Integer prev=(Integer)(node.getPrev().getElem());
	    		Integer next=(Integer)(node.getNext().getElem());
    			String s1;
	    		String s2;
	    		if(prev==null){
	    			s1="该元素为第一元素无前元素";
	    		}else{
	    			s1=prev.intValue()+"";
	    		}
    			if(next==null){
	    			s2="该元素为最后一个元素无后元素";
    			}else{
	    			s2=next.intValue()+"";
    			}
    			System.out.println("该元素的前后元素分别为："+s1+","+s2);
	    	}else if(select==3){
    			System.out.println("请输入你要删除的位置,范围是1~"+list.getLength());
	    		int position=s.nextInt();
    			while(position>list.getLength()||position<1){
    				System.out.println("您输入的位置不正确,请重新输入");
    				position=s.nextInt();
    			}
	    		list.removeNode(position);
	    		System.out.println("执行删除后的结果是：");
	    		list.Traversal();
    		}else if(select==4){
    			System.exit(0);
    		}else{
    			System.out.println("您输入的选项有误，请重新输入");
    		}
		}
	}

}