선형구조 - 연결 리스트 구현해보기

Linked List(연결 리스트)

구현

1. 연결 리스트 

import java.util.Comparator;

//연결 리스트 클래스
public class LinkedList<E>{

	// Node클래스
	class Node<E>{
    	private E data;	// 데이터
        private Node<E> next;	// 다음 노드 참조
        
    	// Node클래스 생성자
    	Node(E data, Node<E> next){
    		this.data = data;
        	this.next = next;
    	}
        
    }
    
    
    private Node<E> head;	// 머리 포인터: 머리 노드를 가리킴
    private Node<E> crnt;	// 선택 포인터: 현재 선택한 노드를 가리킴

	//연결 리스트 생성자
	public LinkedList(){
    	//head: 빈 연결 리스트는 노드가 없고 head가 가리킬 곳도 없기 때문에 null을 넣음
        //crnt: 어떤 요소도 선택하지 않게 하기 위해 null을 넣음
    	head = crnt = null;
	}


	//검색, 삭제, 삽입 등의 메서드
}

 

2. 메서드 구현해보기(포인터 이용)

2-1. 검색 메서드

: 검색하는 노드 만날 때까지 머리 노드부터 순서대로 스캔

1) 매개변수

- E obj: 검색 시 키가 되는 데이터 넣어 둔 객체

- Comparator<? super E> c: obj와 노드 안의 데이터를 비교하기 위한 Comparator

     - Comparator<T>: 함수형 인터페이스로 int compare(T t1, T t2)메서드로 두 객체를 비교해 정수, 0, 또는 양수 반환

     - 와일드카드 ?: 제네릭에 들어올 수 있는 어떤 타입이든 지정할 때 쓰는 미지 타입

     - ? super E: 하한 경계로 E 타입 또는 E의 슈퍼타입을 의미

          ex) Comparator<Animal>은 Comparator<? super Dog>에 할당 가능

     => E 타입의 값과 비교할 수 있는 c면 뭐든 비교 허용

          ex) E가 Integer라면 Number, Object를 허용

 

2) 분석

      1. 스캔 노드 참조 변수 ptr을 head로 초기화 - 머리노드

      2. 스캔할 노드가 있는 지 확인

      3. 데이터 obj와 스캔 중인 노드의 데이터 ptr.data를 Comparator c로 비교

           3-1. compare 메서드가 0을 반환하면 종료 및 검색 성공     // 찾고자 하는 값 == 스캔 중인 노드의 값

           3-2. 선택 포인터가 ptr.data를 반환

      4. obj와 ptr.data가 일치하지 않으면 ptr에 ptr.next를 대입해 ptr이 다음 노드를 가리키도록 함

      5. 검색 실패 시 null 반환

3) 시간복잡도: O(n)

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;	//검색 실패
}

 

2-2. 삽입 메서드

1) 머리에 노드 삽입하는 메서드

public void addFirst(E obj){
	Node<E> ptr = head;
    head = crnt = new Node<E>(obj, ptr);
}

 

2) 꼬리에 노드 삽입하는 메서드

      1. 리스트 스캔

      2-1) 리스트가 빈 경우: addFirst(obj);

      2-2) 리스트가 안 빈 경우: 리스트를 순회하여 ptr이 꼬리노드를 가리킬 때 반복문에서 나와 노드를 삽입한다.

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);
    }
}

 

 

2-3. 삭제 메서드

- 해제라고 생각하면 좋을 것 같다

1) 머리노드 삭제하는 메서드

public void removeFirst(){
	if(head != null)//리스트 안 빔
         head = crnt = head.next;
}

 

2) 꼬리노드 삭제하는 메서드

      1. 리스트 스캔

      2-1) 리스트에 노드가 1개인 경우: removeFirst();        //노드가 1개인 리스트라면 head에 null을 대입하면 빈 상태가 된다.

      2-2) 리스트에 노드가 2개 이상인 경우: pre가 꼬리 앞 노드를 ptr이 꼬리노드를 가리키면 pre의 next에 null을 대입한다.

public void removeLast(){
	if(head != null)
    	if(head.next == null)
        	removeFirst();
    else{
    	Node<E> ptr = head;
        Node<E> pre = head;	//ptr의 앞쪽 노드
        while(ptr.next != null){
        	pre = ptr;
        	ptr = ptr.next;
        }
        pre.next = null;
        crnt = pre;
    }
}

 

3) 선택한 노드 삭제하는 메서드

- 삭제할 노드 p가 머리 노드면 removeFirst()

public void remove(Node p){
	if(head != null){
    	if(head.next == null)
        	removeFirst();
        else{
            Node<E> ptr = head;

            while(ptr.next != p){
                ptr = ptr.next;
                if(ptr == null)//리스트에 p가 없음
                    return;
            }
            ptr.next = p.next
            crnt = ptr;
        }
    }
}

 

4) 모든 노드 삭제 메서드

- 머리노드 반복 삭제

public void clear(){
	while(head != null){
    	removeFirst();
    }
    crnt = null;
}