单双链表

MyList接口

public interface<T> extends Iterator<T>{
	public void add(T element);//添加元素element
	public void delete(T element);//删除指定元素
	public void delete(int index);//按照索引删除元素
	public int indexOf(T element);//返回元素索引
	public boolean contains(T element);//是否存在元素element
	public void update(int index,T newElement);//将指定位置元素置换为newElement
	T getElem(int index);//返回index处位置的元素
}
           

ListNode节点

public class ListNode{
	public Object data;//存储的元素
	ListNode pre;//前驱
	ListNode next;//后继
	public ListNode(Object data){//构造函数
		this.data=data;
}
}
           

SingleLinkedList

public class SingleLinkedList<T>implements MyList<T>{
	private ListNode first;//头节点
	private ListNode last;//尾节点
	private int size;//单链表长度
@Override
public void add(T element){
	if(first==null){
		first=new ListNode(element);//生成新节点
		last=first;
}
	else{
		last.next=new ListNode(element);//生成新节点，追加在表尾
		last=last.next;
}
		size++;//表大小加1
}
@Override
public void delete(T element){
	ListNode p=first;
	ListNode pre=null;
	while(p!=null){
		if(p.data.equals(element)){
			if(p==first)first=first.next;
			else{
				pre.next=p.next;//改变指针的指向完成删除
				size--;
				break;
}
}
		pre=p;
		p=p.next;

		
}
}
@Override
public void delete(int index){
	ListNode p=first;
	ListNode pre=null;
	int i=0;
	if(index<0||index>size)//范围错误
	{
		return;
}
	while(p!=null){
		if(i==index){//找到元素
			if(p==first)first=first.next;
			else{
				pre.next=p.next;//改变指针指向删除成功
				size--;
				break;//删除成功
}
			pre=p;
			p=p.next;
			i++;
}	
}
}
@Override
public int indexOf(T element){
	int i=0;
	ListNode p=first;
	while(p!=null){
		if(p.data.equals(element))return i;//存在元素返回该位置索引
		p=p.next;
		i++;
}
	return -1;
}
@Override
public void update(int index,T newElement){
	int i=0;
	ListNode p=first;
	if(index<0||index>size)return;//范围错误
	while(p!=null){
		if(i==index)p.data=newElement;//指定位置元素设为newElement
		p=p.next;
		i++;
}	
}
@Override
public boolean contains(T element){
	ListNode p=first;
	while(p!=null){
		if(p.data.equals(element))return true;//存在元素
		p=p.next;
}
	return false;
}
@Override
public T getElem(int index){
	ListNode p=first;
	int i=0;
	while(p!=null){
		if(i==index)return (T)p.data;//返回index处位置元素
		p=p.next;
		i++;
}
	return null;
}
@Override
public String toString(){
	ListNode p=first;
	StringBuilder sb=new StringBuilder("[");
	while(p!=null){
		sb.append(p.data);
		if(p.next!=null)sb.append(",");
		p=p.next;
}
	sb.append("]");
	return sb.toString();
}
@Override
public boolean hasNext(){
	ListNode p=first;
	return p!=null;
}
@Override
public T next(){
	ListNode str=first;
	first=first.next;
	return (T)str.data;
}
}
           

DoubleLinkedList实现:

public class DoubleLinkedList<T> implements MyList<T>{
	private ListNode first=new ListNode(null);
	private ListNode last=new ListNode(null);
	private int size;
	public DoubleLinkedList(){
		first.next=last;
		last.pre=first;
}
@Override 
public void add(T element){
	ListNode newNode=new ListNode(element);	
		last.pre.next=newNode;
		newNode.pre=last.pre;
		newNode.next=last;
		last.pre=newNode;
		size++;
}
@Override
public void delete(T element){
	ListNode p=first.next;
	while(p!=last){
		if(p.data.equals(element)){
			p.pre.next=p.next;
			p.next.pre=p.pre;
			p.next=null;
			p.pre=null;
			size--;
			break;
}
		p=p.next;
}
}
@Override
public void delete(int index){
	int i=0;
	ListNode p=first.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++;
}
}
@Override
public void update(int index,T newElement){
if(index<0||index>size){
		return;
}
	ListNode p=first.next;
	int i=0;
	while(p!=last){
		if(i==index){
			p.data=newElement;
}	
			i++;
			p=p.next;
}
}
@Override
public boolean contains(T element){
	ListNode p=first.next;
	while(p!=last){
		if(p.data.equals(element))return true;
		p=p.next;
}
	return false;
}
@Override
public int indexOf(T element){
	ListNode p=first.next;
	int i=0;
	while(p!=last){
		if(p.data.equals(element)){
			return i;
}
	p=p.next;
	i++;
}
return -1;
}
@Override 
public T getElem(int index){
	ListNode p=first.next;
	int i=0;
	while(p!=last){
		if(i==index)return (T)p.data;
		i++;
		p=p.next;
}
return null;
}
@Override
public String toString(){
	StringBuilder sb=new StringBuilder("[");
	ListNode p=first.next;
	while(p!=last){
		sb.append(p.data);
		if(p.next!=null)sb.append(",");
		p=p.next;
}
sb.append("]");
return sb.toString();
}
ListNode p=first;
@Override
public boolean hasNext(){
	return p.next!=last;
}
@Override
public T next(){
	ListNode next=p.next;
	p=p.next;
	return(T)next.data;
}
}
           

双链表只是比单链表多了一个指向前驱的指针，删除操作比单链表麻烦一点，其他操作基本类似