单链表的基本操作

单链表图示

单链表的删除节点操作

单链表的添加节点操作（将节点添加到末尾）

单链表的添加节点操作（将节点添加到中间）

定义单链表类

public class NodeList {
    Object object;
	NodeList next;
	public NodeList(Object object) {
		this.object = object;
	}
}

定义操作接口

public interface MyList {
	void delete(int index);
	void delete(Object element);
	void add(Object element);
	void update(int index,Object newElement);
	boolean contains(Object target);
	Object at(int index);
	int indexOf(Object element);

}

定义操作实现类

public class SingleLinkList implements MyList{
	private NodeList head; //头节点
	private NodeList last;
	int size;

	public void delete(int index) {
		if(index<0||index>=size) return;   //处理边界
		int i=0;         //节点的索引
		NodeList p=head;
		NodeList pre=null;
		while(p!=null){
			if(i==index){
				if(p==head){      //如果删除的是头节点
					head=head.next;   //头节点后移
				}else {
					pre.next=p.next;
				}
				size--;
				break;
			}
			pre=p;         //前驱指针后移
			p=p.next;     //p指针后移
			i++;
		}

	}

	public void delete(Object element) {
		NodeList p=head;    //头本身不能动
		NodeList pre=null;  //p节点的前一个节点    相当于p的前驱   因为是单链表   要实现删除的话   必须要2个指针挨着移动才可以
		while(p!=null){
			if(p.object.equals(element)){
				if(p==head){     //如果删除的是头部节点
					head=head.next;       //将头部节点后移
				}else {
					pre.next=p.next;
				}
				size--;
				break;    //删除元素后  没必要再继续移动了
			}
			pre=p;        //前驱指针后移
			p=p.next;     //p指针后移
		}

	}

	public void add(Object element) {
		if(head==null){                   //链表为空
			head=new NodeList(element);
			last=head;          //头节点   尾节点都是这个节点
		}else {
			last.next=new NodeList(element);
			last=last.next;   //尾指针后移
		}
		size++;          //链表的大小+1

	}

	public void update(int index, Object newElement) {
		if(index<0||index>=size) return; //处理边界
		int i=0;         //节点的索引
		NodeList p=head;
		while(p!=null){
			if(i==index){
				p.object=newElement;
				break;
			}
			p=p.next;     //p指针后移
			i++;
		}
	}

	public boolean contains(Object target) {
		NodeList p=head;
		while(p!=null){
			if(p.object.equals(target)){
				return true;
			}
			p=p.next;     //p指针后移
		}
		return false;
	}

	public Object at(int index) {
	if(index<0||index>=size) return null; //处理边界
		int i=0;         //节点的索引
		NodeList p=head;
		while(p!=null){
			if(i==index){
				return p.object;
			}
			p=p.next;     //p指针后移
			i++;
		}
		return null;
	}

	public int indexOf(Object element) {
		int i=0;         //节点的索引
		NodeList p=head;
		while(p!=null){
			if(p.object.equals(element)){
				return i;
			}
			p=p.next;     //p指针后移
			i++;
		}
		return -1;
	}





	@Override
	public String toString() {
	NodeList p=head;    //不要随便去动原来的饿头节点  因此复制一份
		StringBuilder sb=new StringBuilder("[");
		while(p!=null){
			sb.append(p.object);
			p=p.next;
			if(p!=null){
				sb.append(",");
			}
		}
		sb.append("]");
		return sb.toString();
	}
}

双链表的基本操作

双链表图示

双链表删除节点

双链表添加节点

双链表定义类

public class DoubleListNode {
	 DoubleListNode next;     //前驱
	 DoubleListNode pre;      //后继
	 Object data;


	public DoubleListNode(Object data) {
		this.data = data;
	}
}

定义接口操作

public interface MyList {
	void delete(int index);
	void delete(Object element);
	void add(Object element);
	void update(int index,Object newElement);
	boolean contains(Object target);
	Object at(int index);
	int indexOf(Object element);

}

双链表操作实现类

public class DoubleNode implements MyList {
	//将头节点和最后一个节点赋空     实际的第一个元素是head.next
	private DoubleListNode head=new DoubleListNode(null);
	private DoubleListNode last=new DoubleListNode(null);
	private int size;

	public DoubleNode() {      //初始化空的双链表
		head.next=last;
		last.pre=head;
	}

	public void delete(int index) {
		if(index<0||index>=size) return;
		int i=0;
		DoubleListNode p=head.next;
		while(p!=last){
			if(i==index){
				p.pre.next=p.next;
				p.next.pre=p.pre;
				//更快的被垃圾回收
				p.next=null;
				p.pre=null;
				size--;
				break;
			}
			p=p.next;
			i++;
		}
	}

	public void delete(Object element) {
		DoubleListNode p=head.next;
		while(p!=last){
			if(p.data.equals(element)){
					//只需要维护2条指针即可
					p.pre.next=p.next;
					p.next.pre=p.pre;
					//为什么要加这2条语句   为了更快的成为垃圾回收对象
					p.pre=null;
					p.next=null;
					size--;
					break;
				}
			p=p.next;
		}
	}

	public void add(Object element) {
		DoubleListNode newNode=new DoubleListNode(element);
		//维护了四条指针   如果不明白可以看图帮助
		last.pre.next=newNode;
		newNode.next=last;
		newNode.pre=last.pre;
		last.pre=newNode;
		size++;
	}

	public void update(int index, Object newElement) {
		if(index<0||index>=size)return;
		DoubleListNode p=head.next;
		int i=0;
		while (p != last) {
			if(i==index){
				p.data=newElement;
				break;
			}
			i++;
			p=p.next;
		}
	}

	public boolean contains(Object target) {
		DoubleListNode p=head.next;
		while(p!=last){
			if(p.data.equals(target)){
				return true;
			}
			p=p.next;
		}
		return false;
	}

	public Object at(int index) {
		DoubleListNode p=head.next;
		int i=0;
		while(p!=last){
			if(i==index){
				return p.data;
			}
			i++;
			p=p.next;
		}
		return null;
	}

	public int indexOf(Object element) {
		DoubleListNode p=head;
		int i=0;
		while(p!=last){
			if(p.data.equals(element)){
				return i;
			}
			i++;
			p=p.next;
		}
		return -1;
	}


	@Override
	public String toString() {
		StringBuilder sb=new StringBuilder("[");
		DoubleListNode p=head.next;
		while(p!=last){
			sb.append(p.data);
			if(p.next!=last) {
				sb.append(",");
			}
			p=p.next;
		}
		return sb.toString();
	}
}

注：上述图示是根据代码画出来的，不一定和教材上的相同，可能有所差异，请读者自行鉴别