자바전문가그룹

글번호 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();
  }
   
}