링크 리스트 의 간단 한 실현

체인 선형 표 는 데이터 구조 에서 매우 간단 하지만 흔히 볼 수 있 는 데이터 구조 로 순서대로 저 장 된 선형 표 에 비해 추가 와 삭제 작업 을 더욱 빨리 실현 할 수 있 으 나 읽 기 속 도 는 순서 구조 보다 느리다.체인 선형 표 의 관건 은 모든 데 이 터 를 노드 형식 으로 저장 하 는 것 이다.데이터 만 저장 하 는 것 이 아니 라 다음 노드 를 가리 키 는 'next' 참조 도 있 습 니 다.체인 구 조 는 양 방향 링크, 순환 링크 등 으로 도 확장 할 수 있다.기본 원 리 는 같 지만 인용 만 늘 렸 다.다음은 가장 간단 한 체인 선형 표 의 실현 소스 코드 입 니 다. 잠재 적 인 bug 가 있 을 것 입 니 다. 그렇지 않 으 면 모든 사람 이 바 텀 데이터 구 조 를 쓸 수 있 습 니 다!그러나 우리 가 이런 데이터 구 조 를 이해 하 는 데 영향 을 주지 않 는 다.

package mywork.c20150605;

import mywork.c20150605.LinkList.Node;

/*
 * a simple demo for LinkList
 * HanChun 2015.6.5
 */

public class LinkListDemo {

	class Node{
		T data;
		Node next;
		
		public Node(){
			
		}
		
		public Node(T data, Node next){
			this.data = data;
			this.next = next;
		}
	}
	
	Node header;
	Node tail;
	int size;								//        
	
	public LinkListDemo(){
		header = null;
		tail = null;
	}
	
	public LinkListDemo(Node element){
		header = element;
		tail = header;
		size++;
	}
	
	//       
	public int getSize(){
		return size;
	}
	
	//         
	public boolean isEmpty(){
		if(size == 0){
			return true;
		}
		return false;
	}
	
	//       
	public Node getNodeByIndex(int index){
		if(index < 0 || index > size){
			throw new IndexOutOfBoundsException("    ");
		}
		Node current = header;
		for(int i = 0; i < size && current != null; current = current.next, i++){
			if(i == index){
				return current;
			}
		}
		return null;
	}
	
	//             
	public int locate(T element){
		Node current = header;
		for(int i = 0; i < size && current != null; current = current.next, i++ ){
			if(current.data.equals(element)){
				return i;
			}
		}
		return -1;
	}
	
	/*
	 *               ，   ：        
	 *            ，        ，      
	 *      。
	 */
	public void addAtHeader(T element){
		header = new Node(element, header);
		if(tail == null){
			tail = header;
		}
		size++;
	}
	
	//       
	public void add(T element){
		if(header == null){
			header = new Node(element, null);
			tail = header;
		}else{
			Node newNode = new Node(element, null);
			tail.next = newNode;
			tail = newNode;
		}
		size++;
	}
	
	//         
	public void insert(T element, int index){
		if(index < 0 || index > size){
			throw new IndexOutOfBoundsException("    ");
		}
		if(header == null){
			add(element);
		}else{
			if(index == 0){
				addAtHeader(element);
			}else{
				Node prev = getNodeByIndex(index - 1);
				prev.next = new Node(element, prev.next);
			}
		}
		size++;
	}
	
	/*
	 *         ,       ，           ，   
	 *        NuLLPointException
	 */
	public void delete(int index){
		if(index < 0 || index > size){
			throw new IndexOutOfBoundsException("    ");
		}
		if(index == 0){
			header = header.next;
		}else{
			Node prev = getNodeByIndex(index - 1);
			Node del = prev.next;
			prev.next = del.next;
			del = null;
		}
		size--;
	}
	
	public String toString(){
		if(isEmpty()){
			return "[]";
		}
		StringBuilder sb = new StringBuilder("[");
		for(Node current = header; current != null ; current = current.next){
			sb.append(current.data.toString() + ",");
		}
		int len = sb.length();
		return sb.delete(len-1, len).append("]").toString();
	}
}