單雙連結清單

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;
}
}
           

雙連結清單隻是比單連結清單多了一個指向前驅的指針，删除操作比單連結清單麻煩一點，其他操作基本類似