리스트 (1)

리스트는 데이터를 순서대로 나열한 자료구조입니다.

위와 같이 선형 구조를 갖는 리스트에는 선형 리스트와 연결 리스트가 있습니다.

• 선형 리스트는 데이터가 배열처럼 연속하는 메모리 공간에 저장되어 순서를 갖습니다.
• 연결 리스트는 메모리가 메모리 공간에 연속적으로 저장되어 있지 않더라도 각각의 데이터 안에 다음 데이터에 대한 정보를 갖고 있어 서로 연결됩니다.
  아래 그림은 연결 그래프의 한 예시 입니다. 데이터가 순서대로 나열되어 있고, 각각의 데이터가 화살표로 연결되어 있습니다.
  
  리스트에 있는 개별 요소를 노드라고 합니다. 노드의 구성 요소는 데이터와 다음 노드를 가리키는 포인터 입니다. 그리고 처음에 있는 노드를 머리노드라고 하며, 끝에 있는 노드를 꼬리노드라고 합니다.
  그리고 앞쪽에 있는 노드를 앞쪽노드, 바로 뒤쪽에 있는 노드를 다음노드라고 합니다.

하지만 배열로 선형 리스트는 쌓이는 데이터의 최대 크기를 미리 알아야하며, 데이터를 삽입, 삭제시 많은 데이터를 옮겨야 하므로 효율이 좋지 않습니다.

포인터로 연결 리스트 만들기

리스트에 데이터를 삽입할 때 노드용 객체를 만들고 삭제할 때 노드용 객체를 없애면 배열로 리스트를 만들 때 발생하는 문제를 해결할 수 있습니다.
이런 노드를 구현하는 방법이 아래와 같습니다. 이런 클래스 구조를 자기참조형 이라고 합니다.

Node < E > 는 제네릭을 구현되므로 임의의 클래스형이 허용됩니다.
그렇게 되는 이유는 필드 data의 자료형인 E가 참조형이므로 클래스형 변수 data가 나타내는 것이 데이터 그 자체가 아니라 데이터를 넣어두는 인스턴스에 대한 참조이기 때문입니다.
다음 노드를 참조하는 next를 뒤쪽 포인터라고 부르면 뒤쪽 포인터 next에 넣어두는 것은 다음 노드에 대한 참조입니다. 다만 다음 노드가 없는 꼬리 노드의 뒤쪽 포인터 값은 null을 참조하도록 합니다.

public class LinkedList<E> {
	// 노드
    class Node<E> {
    	private E data;
        private Node<E> next;
        
        // 생성자
        Node(E data, Node<E> next){
        	this.data = data;
        	this.next = next;
        }
    
    }   
    
}

private Node<E> head;	// 머리 포인터(머리 노드 참조)
private Node<E> crnt;	// 선택 포인터(선택 노드 참조)

노드 클래스 Node< E >

연결 리스트 클래스 Linked List< E > 안에 선언되어 있습니다. 이 클래스에는 다음과 같이 두 필드와 생성자가 있습니다.

연결 리스트 클래스 LinkedList < E >

다음과 같이 두 필드가 있습니다.

아래는 연결 리스트 클래스의 이미지를 나타냅니다. 리스트에 있는 각 노드는 Node< E >형입니다. 연결 리스트 클래스가 갖는 데이터는 실질적으로 머리 포인터 head뿐 입니다.

생성자 LinkedList

연결 리스트 클래스 LinkedList< E >의 생성자는 노드가 하나도 없는 비어 있는 연결 리스트를 생성합니다.

public LinkedList(){
	head = crnt = null;
}

이 생성자는 머리 포인터 head에 null을 대입합니다. Node< E >형 변수 head가 머리 노드에 대한 참조이지 머리 노드 그 자체가 아님에 주의해야 합니다. 비어 있는 연결리스트는 노드도 없고 head가 가리키는 곳도 없으므로 그 값을 null로 합니다. 그리고 crnt에도 null을 넣어 어떤 요소도 선택하지 않도록 합니다.

• 연결 리스트가 비어있는지 판단하는 방법: a는 노드가 하나도 없는 상태입니다.

• 노드가 1개인 연결 리스트를 판단하는 방법: b는 연결 리스트에 노드가 1개만 있는 상태입니다. 머리 포인터 head가 가리키는 곳은 머리노드 A입니다. 머리노드 A는 리스트의 꼬리 노드이기도 하므로 그 뒤쪽 포인터 값은 null입니다.

• 노드가 2개인 연결 리스트를 판단하는 방법: C는 노드가 2개 있는 상태입니다. 머리노드는 A, 꼬리노드는 B입니다. 이때 head가 가리키는 노드 A의 next는 노드 B를 가리킵니다.

• 꼬리 노드인지 판단하는 방법: Node< E > 형의 변수 p가 리스트의 노드 중 하나를 가리킬 때 변수 p가 가리키는 노드가 연결 리스트의 꼬리노드인지 판단하는 방법은 p.next == null입니다.

검색을 수행하는 메서드 search

public E search(E obj, Comparator<? super E> c) {
        Node<E> ptr = head;         // 현재 스캔 중인 노드

        while (ptr != null) {
            if (c.compare(obj, ptr.data) == 0) {  // 검색 성공
                crnt = ptr;
                return ptr.data;
            }
            ptr = ptr.next;   // 뒤쪽 노드에 주목
        }
        return null;    // 검색 실패
    }

검색에 사용하는 알고리즘은 선형 검색이고 검색하는 노드를 만날때까지 머리 노드부터 순서대로 스캔합니다.

• 노드 스캔은 다음 조건 중 어느 하나가 성립하면 종료합니다.

  1. 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우.
  2. 검색 조건을 만족하는 노드를 찾은 경우.

  머리에 노드를 삽입하는 메서드 addFirst

  리스트 머리에 노드를 삽입합니다.

     //--- 머리 노드 삽입 ---//
     public void addFirst(E obj) {
         Node<E> ptr = head;                       // 삽입 전의 머리 노드
         head = crnt = new Node<E>(obj, ptr);
     }

  꼬리에 노드를 삽입하는 메서드 addLast

  꼬리에 노스트를 삽입합니다. 리스트가 비어 있는지 아닌지를 먼저 확ㅇ니하고 경우에 따라 처리합니다.

      //--- 꼬리 노드 삽입 ---//
     public void addLast(E obj) {
         if (head == null)                // 리스트가 비어있으면
             addFirst(obj);               // 머리에 삽입
         else {
             Node<E> ptr = head;
             while (ptr.next != null)
                 ptr = ptr.next;
             ptr.next = crnt = new Node<E>(obj, null);
         }
     }

  머리 노드를 삭제하는 메서드 removeFirst

  리스트가 비어있지 않을때만 머리 노드를 삭제를 실행합니다.

  
     //--- 머리노드 삭제 ---//
     public void removeFirst() {
         if (head != null)        // 리스트가 비어있지 않으면
             head = crnt = head.next;
     }

  꼬리 노드를 삭제하는 메서드 removeLast

  리스트에 노드가 몇 개 있는지에 따라 다음과 같이 처리합니다.

      //--- 꼬리노드 삭제 ---//
     public void removeLast() {
         if (head != null) {
             if (head.next == null)             // 노드가 하나만 있으면
                 removeFirst();                 // 머리노드 삭제
             else {
                 Node<E> ptr = head;            // 스캔 중인 노드
                 Node<E> pre = head;            // 스캔 중인 노드의 앞쪽 노드
  
                 while (ptr.next != null) {
                     pre = ptr;
                     ptr = ptr.next;
                 }
                 pre.next = null;                // pre는 삭제 뒤의 꼬리 노드
                 crnt = pre;
             }
         }
     }

  선택한 노드를 삭제하는 메서드 remove

    //--- 노드p 삭제 ---//
     public void remove(Node p) {
         if (head != null) {
             if (p == head)                // p가 머리 노드이면
                 removeFirst();            // 머리 노드 삭제
             else {
                 Node<E> ptr = head;
  
                 while (ptr.next != p) {
                     ptr = ptr.next;
                     if (ptr == null) return;    // p가 리스트에 없음
                 }
                 ptr.next = p.next;
                 crnt = ptr;
             }
         }
     }
  
     //--- 선택 노드 삭제 ---//
     public void removeCurrentNode() {
         remove(crnt);
     }
  
     //--- 전체노드 삭제 ---//
     public void clear() {
         while (head != null)        // 비게 될 때까지
             removeFirst();          // 머리 노드 삭제
         crnt = null;
     }
  
     //--- 선택 노드를 하나 뒤쪽으로 진행 ---//
     public boolean next() {
         if (crnt == null || crnt.next == null)
             return false;           // 나아갈 수 없음
         crnt = crnt.next;
         return true;
     }

  선택 노드 하나를 뒤쪽으로 진행시키는 메서드 next

  선택 노드를 하나 뒤쪽으로 나아가도록 하는 메서드로 리스트가 비어있지 않고 선택 노드의 뒤쪽 노드가 있을 때만 선택 노드를 하나 뒤쪽으로 진행시킵니다.
  선택 노드가 나아가면 true, 그렇지 않으면 false를 반환합니다.

     //--- 선택 노드 표시 ---//
     public void printCurrentNode() {
         if (crnt == null)
             System.out.println("노드가 없습니다.");
         else
             System.out.println(crnt.data);
     }
  	
      //--- 선택 노드를 하나 뒤쪽으로 진행 ---//
     public boolean next() {
         if (crnt == null || crnt.next == null)
             return false;           // 나아갈 수 없음
         crnt = crnt.next;
         return true;
     }

선택 노드를 출력하는 메서드 printCurrentNode

선택 노드를 출력하는 메서드로 crnt가 참조하는 노드의 데이터 crnt.data에 대해 묵시적으로 문자열을 반환하여, 곧 toString 메서드를 호출하여 그 결과로 얻어지는 문자열을 보여줍니다. 다만, 선택 노드가 없는 경우 노드가 없다고 출력합니다.

모든 노드를 출력하는 메서드 dump

리스트의 순서대로 모든 노드를 출력합니다. 머리노드부터 꼬리노드까지 스캔하면서 각 노드의 데이터 ptr.data를 출력합니다. 이 메서드는 선택 crnt값을 업데이트하지 않습니다.

   //--- 전체 노드 표시 ---//
   public void dump() {
       Node<E> ptr = head;

       while (ptr != null) {
           System.out.println(ptr.data);
           ptr = ptr.next;
       }
   }