用鏈表實現(xiàn)線性表

鏈表接口

public interface ListInterface<T> {		public boolean add(T newEntry);		public boolean add(int newPosition,T newEntry);		public T remove(int givenPosition);		public void clear();		public boolean replace(int givenPosition,T newEntry);		public T getEntry(int givenPosition);		public boolean contains(T anEntry);		public int getLength();		public boolean isEmpty();		public boolean isFull();		public void display();}
鏈表實現(xiàn)類
鏈表是由一個個結(jié)點（Node）組成的，而結(jié)點應該是實現(xiàn)類所私有的，應該定義成內(nèi)部類。單向鏈表的結(jié)點有兩個數(shù)據(jù)域，一個引用線性表中的元素，一個引用另一個結(jié)點。
public class Linked_list<T> implements ListInterface<T>{	PRivate Node firstNode;	private int length;		public Linked_list() {		firstNode=null;		length=0;	}		private Node getNodeAt(int givenPosition){		assert !isEmpty() && givenPosition>=1 && givenPosition<=length;		Node currentNote=firstNode;		for(int i=1;i<givenPosition;i++){			currentNote=currentNote.next;		}		assert currentNote!=null;		return currentNote;	}		@Override	public boolean add(T newEntry) {		Node newNode=new Node(newEntry);		if(isEmpty())			firstNode=newNode;		else{			Node lastNode=getNodeAt(length);			lastNode.next=newNode;		}		length++;		return true;	}	@Override	public boolean add(int newPosition, T newEntry) {		boolean isSuccessful=true;		if(newPosition>=1 && newPosition<=length+1){			Node newNode=new Node(newEntry);			if(isEmpty() || newPosition==1){				newNode.next=firstNode;				firstNode=newNode;			}else{				Node beforeNode=getNodeAt(newPosition-1);				Node afterNode=beforeNode.next;				beforeNode.next=newNode;				newNode.next=afterNode;			}			length++;		}else			isSuccessful=false;		return isSuccessful;	}	@Override	public T remove(int givenPosition) {		T result=null;		if(!isEmpty() && givenPosition>=1 && givenPosition<=length){			if(givenPosition==1){				result=firstNode.element;				firstNode=firstNode.next;			}else{				Node beforeNode=getNodeAt(givenPosition-1);				Node ToremoveNode=beforeNode.next;				Node afterNode=ToremoveNode.next;				result=ToremoveNode.element;				beforeNode.next=afterNode;			}			length--;		}		return result;	}	@Override	public final void clear() {		firstNode=null;		length=0;	}	@Override	public boolean replace(int givenPosition, T newEntry) {		boolean isSuccessful=true;		if(!isEmpty() && givenPosition>=1 && givenPosition<=length){			Node desiredNode=getNodeAt(givenPosition);			desiredNode.element=newEntry;		}else			isSuccessful=false;		return isSuccessful;	}	@Override	public T getEntry(int givenPosition) {		T result=null;		if(!isEmpty() && givenPosition>=1 && givenPosition<=length){			Node desiredNode=getNodeAt(givenPosition);			result=desiredNode.element;		}		return result;	}	@Override	public boolean contains(T anEntry) {		boolean isSuccessful=false;		Node currentNode=firstNode;		while (currentNode!=null) {			if(currentNode.element.equals(anEntry)){				isSuccessful=true;				break;			}			currentNode=currentNode.next;		}		return isSuccessful;	}	@Override	public int getLength() {		return length;	}	@Override	public boolean isEmpty() {		return length==0;	}	@Override	public boolean isFull() {		return false;	}	@Override	public void display() {		Node currentNode=firstNode;		while (currentNode!=null) {			System.out.print(currentNode.element+" ");			currentNode=currentNode.next;		}		System.out.println();	}		private class Node {		private T element;		private Node next;		private Node(T element) {			this(element,null);		}				private Node(T element,Node next){			this.element=element;			this.next=next;		}	}}
測試代碼
public class main_Link {	private static Linked_list<Integer> list;	public static void main(String[] args) {		list=new Linked_list<Integer>();		for(int i=1;i<=20;i++)			list.add(i);		list.add(11, 24);		list.display();		list.remove(13);		list.display();		list.replace(19, 56);		list.display();		System.out.println(list.getEntry(19));		if(list.contains(56))			System.out.println("包含了");		System.out.println("鏈表長度："+list.getLength());			}}1 2 3 4 5 6 7 8 9 10 24 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 24 11 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 24 11 13 14 15 16 17 18 56 20 56包含了鏈表長度：20......................................................................................................華麗分割線........................................................................................................因為Node是內(nèi)部類，則Linked_list類可以按名稱直接訪問Node的私有數(shù)據(jù)域。然而一些計算機科學家認為，應該使用getter和setter方法訪問類的數(shù)據(jù)域。并且可以實現(xiàn)迭代器來歷遍鏈表的數(shù)據(jù)，從而代替上述display()函數(shù)。
鏈表接口擴展
public interface ListWithIteratorInterface<T> extends ListInterface<T>{	public Iterator<T> getIterator();}
鏈表實現(xiàn)類
public class LinkedListWithIterator<T> implements ListWithIteratorInterface<T>{		private Node firstNode;	private int length;		public LinkedListWithIterator() {		firstNode=null;		length=0;	}	private Node getNodeAt(int givenPosition){		assert !isEmpty() && givenPosition>=1 && givenPosition<=length;		Node currentNote=firstNode;		for(int i=1;i<givenPosition;i++){			currentNote=currentNote.getNextNode();		}		assert currentNote!=null;		return currentNote;	}		@Override	public boolean add(T newEntry) {		Node newNode=new Node(newEntry);		if(isEmpty())			firstNode=newNode;		else{			Node lastNode=getNodeAt(length);			lastNode.setNextNode(newNode);;		}		length++;		return true;	}	@Override	public boolean add(int newPosition, T newEntry){		boolean isSuccessful=true;		if(newPosition>=1 && newPosition<=length+1){			Node newNode=new Node(newEntry);			if(isEmpty() || newPosition==1){				newNode.setNextNode(firstNode);;				firstNode=newNode;			}else{				Node beforeNode=getNodeAt(newPosition-1);				Node afterNode=beforeNode.getNextNode();				beforeNode.setNextNode(newNode);				newNode.setNextNode(afterNode);			}			length++;		}else			isSuccessful=false;		return isSuccessful;	}	@Override	public T remove(int givenPosition) {		T result=null;		if(!isEmpty() && givenPosition>=1 && givenPosition<=length){			if(givenPosition==1){				result=firstNode.getData();				firstNode=firstNode.getNextNode();			}else{				Node beforeNode=getNodeAt(givenPosition-1);				Node ToremoveNode=beforeNode.getNextNode();				Node afterNode=ToremoveNode.getNextNode();				result=ToremoveNode.getData();				beforeNode.setNextNode(afterNode);;			}			length--;		}		return result;	}	@Override	public void clear() {		firstNode=null;		length=0;	}	@Override	public boolean replace(int givenPosition, T newEntry) {		boolean isSuccessful=true;		if(!isEmpty() && givenPosition>=1 && givenPosition<=length){			Node desiredNode=getNodeAt(givenPosition);			desiredNode.setData(newEntry);;		}else			isSuccessful=false;		return isSuccessful;	}	@Override	public T getEntry(int givenPosition) {		T result=null;		if(!isEmpty() && givenPosition>=1 && givenPosition<=length){			Node desiredNode=getNodeAt(givenPosition);			result=desiredNode.getData();		}		return result;	}	@Override	public boolean contains(T anEntry) {		boolean isSuccessful=false;		Node currentNode=firstNode;		while (currentNode!=null) {			if(currentNode.element.equals(anEntry)){				isSuccessful=true;				break;			}			currentNode=currentNode.getNextNode();		}		return isSuccessful;	}	@Override	public int getLength() {		return length;	}	@Override	public boolean isEmpty() {		return length==0;	}	@Override	public boolean isFull() {		return false;	}	@Override	public void display() {		Iterator iterator=getIterator();		while(iterator.hasNext()){			System.out.print(iterator.next()+" ");		}		System.out.println();	}	@Override	public Iterator<T> getIterator() {		return new IteratorForLinkedList();	}			/**	 * 內(nèi)部類迭代器	 * @author Administrator	 *	 */	private class IteratorForLinkedList implements Iterator<T>{		private Node nextNode;				private  IteratorForLinkedList() {			this.nextNode=firstNode;		}		@Override		public boolean hasNext() {			return nextNode!=null;		}		@Override		public T next() {			if(hasNext()){				Node returnNode=nextNode;				nextNode=nextNode.getNextNode();				return returnNode.element;			}else				throw new NoSuchElementException("Illegal call to next();"+"iteration is after end of list.");		}		public void remove(){//不允許在歷遍過程中刪除			throw new UnsupportedOperationException("remove() is not suported.");		}			}	private class Node {		private T element;		private Node next;		private Node(T element) {			this(element,null);		}				private Node(T element,Node next){			this.element=element;			this.next=next;		}				private T getData(){			return element;		}				private void setData(T newData){			element=newData;		}				private Node getNextNode(){			return next;		}				private void setNextNode(Node nextNode){			next=nextNode;		}	}}