내용

글번호 818
작성자 허진경
작성일 2018-02-22 10:08:44
제목 SingleLinkedList 주석 포함
내용 자바로 구현한 단일연결리스트 SingleLinkedList.java
//단일 연결리스트를 구현한 클래스
public class SingleLinkedList<E> {
	
	//노드 정보를 저장하는 클래스
	private class Node<T> {
		private T data;		//데이터 필드
		private Node<T> next;	//주소 필드(다음 노드를 가리킴)
		
		//데이터를 인수로 받아 노드 객체를 생성하는 생성자
		public Node(T data) {
			this.data = data;
			this.next = null;
		}
		
		//데이터를 문자열로 반환하는 메서드
		@Override
		public String toString() {
			return String.valueOf(data);
		}
	}
	
	private Node<E> head = null;	//헤드 노드, 맨처음 노드를 찾기 위해 반드시 필요
	private int size = 0;			//노드의 수를 저장
	private Node<E> tail = null;	//가장 마지막 노드를 저장하는 변수, 성능을 높일 수 있다.

	//노드의 엘리먼트를 []와 콤마로 분리해서 문자열로 반환하는 메서드
	//연결리스트의 엘리먼트를 출력하기 위해
	public String toString() {
	    if(head == null){
	        return "[]";
	    }       
	    Node<E> temp = head;	//temp 변수를 두는 이유는? head 정보를 잃지 않기 위해
	    String str = "[";
	    while(temp.next != null){
	        str += temp.data + ",";
	        temp = temp.next;
	    }
	    str += temp.data;
	    return str+"]";
	}
	
	//전용 메서드, add(E), add(int,E) 메서드에서 사용
	//맨 앞에 노드를 추가
	private void addFirst(E input){
	    Node<E> newNode = new Node<>(input);
	    newNode.next = head; 	//삭제하면 안됨, add(0, E)할 때 필요
	    head = newNode;
	    size++;
	    if(head.next == null){	//새로 추가된 노드가 가장 마지막 노드이다.
	        tail = head; 		//tail = newNode와 동일
	    }
	}

	//가장 마지막에 노드를 추가, 전용 메서드
	private void addLast(E input){
	    Node<E> newNode = new Node<>(input);
	    if(size == 0){
	        addFirst(input);
	    } else {
	        tail.next = newNode; //가장 마지막 노드가 가리키는 노드는 새로 추가되는 노드임
	        tail = newNode;	//새로 추가된 노드가 가장 마지막 노드가 되어야 함
	        size++;
	    }
	}
	
	//공용메서드, 사용자의 편의를 위해서 제공
	public void add(E input){
	    addLast(input);
	}
	
	//주어진 위치에 엘리먼트를 삽입, index 위치에
	//index위치의 전(Previous)노드를 찾아야 함
	public void add(int index, E input){
	    if(index == 0){
	        addFirst(input);	//인덱스가 0이면 맨 앞에
	    } else if(index == size) {
	    	addLast(input);		//인덱스가 size이면 맨 마지막 노드 뒤에
	    } else if(index > size || index < 0) { //인덱스 범위를 넘어서면
	    	throw new IndexOutOfBoundsException(String.valueOf(index)); //예외를 발생시킴
	    	//RuntimeException의 하위 예외, throws 없어도 됨,but 인데스가 범위를 벗어나면 예외 발생
	    	//add(int, E)를 호출하는 곳에서 try~catch블록으로 예외 처리 해 줄것을 권장.
	    } else {
	        Node<E> prev = head;
	        //추가하려는 노드의 전전 노드를 알면 전전노드.next를 전노드에 할당
	        for (int i=0; i<index-1; i++) { 
	            prev = prev.next;
	        }
	        Node<E> newNode = new Node<>(input);
	        newNode.next = prev.next;	// 1
	        prev.next = newNode;		// 2
	        size++;
//	        if(newNode.next == null){	//가장 마지막 노드일 경우
//	            tail = newNode;
//	        }
	    }
	}// main에서 list.add(2, "F");로 테스트 해 보세요.
	
	//가장 처음 노드를 삭제, head가 처음노드.next를 가리키도록 해야 함
	//삭제할 경우는 삭제하는 노드의 값을 반환. 
	public E removeFirst(){
	    Node<E> temp = head;
	    head = temp.next;
	    E data = temp.data;
	    temp = null;
	    size--;
	    return data;
	}
//	public void removeFirst() {} //안됨, 리턴타입만 다르게 중복 정의 안됨
	
	//인덱스를 이용해 노드를 삭제
	public E remove(int index){
	    if(index == 0) {
	        return removeFirst();
	    }else if(index >= size || index < 0) {
	    	//인덱스가 범위를 넘어서면 예외를 발생시킴
	    	throw new IndexOutOfBoundsException(String.valueOf(index));
	    }
	    Node<E> prev = head;
        for (int i=0; i<index-1; i++) {// 삭제하려는 노드의 전노드를 찾음
            prev = prev.next;
        }

        Node<E> todoDeleted = prev.next;//별도의 변수로 저장하는 이유는? null을 할당해서 소멸시키기 위해
        prev.next = prev.next.next; 	//prev.next = todoDeleted.next;와 동일

	    E returnData = todoDeleted.data; 
	    if(todoDeleted == tail){
	        tail = prev;
	    }

	    todoDeleted = null; 			//null을 할당해서 소멸시킴(GC Thread에의 Garbage Connection 대상)
	    size--;
	    return returnData;
	}
	
	//인덱스로 데이터를 조회
	public E get(int index){
		if(index < 0 || index >= size) {
			throw new IndexOutOfBoundsException(String.valueOf(index));
		}
	    Node<E> temp = head;
        for (int i=0; i<index; i++) { //인덱스 위치의 노드를 찾아야 함
            temp = temp.next;
        }
	    return temp.data;
	}
	
	//노드의 수를 반환하는 메서드
	public int size() {
		return size;
	}
	
	//데이터를 이용해 인덱스를 찾는 메서드
	public int indexOf(E data){
	    Node<E> temp = head;
	    int index = 0;
 
	    //객체는 ==연산자와 equals()에 의해 동등 비교
	    //주소가 다르면 내용이 다른지도 확인해야 합니다.
	    while( (temp.data != data) && (!temp.data.equals(data)) ){
	        temp = temp.next;
	        index++;
	        if(temp == null) {
	            return -1;
	        }
	    }
	    return index;
	}
	
	//연결리스트의 내용을 배열로 반환하는 메서드
	public Object[] toArray() {
		Object[] listArray = new Object[size];
		for(int i=0; i<size; i++) {
			listArray[i] = get(i);
		}
		return listArray;
	}
	
	//지정한 유형 배열로 반환하는 메서드
	//사용법 : String[] listArr = list.toArray(new String[list.size()]);
	public E[] toArray(E[] e) {
		E[] listArray = e;
		for(int i=0; i<size; i++) {
			listArray[i] = get(i);
		}
		return listArray;
	}

	//연결리스트를 테스하기 위한 코드
	public static void main(String[] args) {
		//String을 데이터로 갖는 연결리스트 객체 생성
		//publci class SingleLinkedList<E> { ... }
		//String 데이터만 리스트에 add()할 수 있음
		SingleLinkedList<String> list = new SingleLinkedList<String>();
		
		System.out.println(list);					  //[]
		list.add("A");		System.out.println(list); //[A]
		list.add("B"); 
		list.add("D");		System.out.println(list); //[A,B,D]
		list.add(2, "F");	System.out.println(list); //[A,B,F,D]
		list.removeFirst();	System.out.println(list); //[B,F,D]
		list.remove(1);		System.out.println(list); //[B,D]
		list.add("C"); 
		list.add("E");		System.out.println(list); //[B,D,C,E]
		System.out.println(list.get(0));	//B
		System.out.println(list.get(1));	//D
		System.out.println(list.get(2));	//C
		System.out.println(list.get(3));	//E
		System.out.println(list.indexOf("A"));	//-1
		System.out.println(list.indexOf("C"));	//2
		System.out.println(list.indexOf(new String("C"))); //2
		
		String[] strArray = list.toArray(new String[list.size]);
		for(String data : strArray) {
			System.out.print(data + " ");
		}//B D C E
		System.out.println();
	}
	
}