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

지난 글 : [알고리즘/Do it 알고리즘] - 리스트

 

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

리스트에 데이터를 삽입할 때 노드용 객체를 만들고 삭제할 때 노드용 객체를 없애면 배열로 리스트를 만들 때 발생하는 문제를 해결할 수 있다. 이런 노드를 구현하는 것이 아래 클래스 Node<E>다.

class Node<E> {
    E data;			//데이터를 참조
    Node<E> next;		//다음 노드를 참조
}

Node<E>는 제네릭으로 구현되므로 데이터형 E는 임의의 클래스형이 허용된다. Node<E>의 이미지를 좀 더 엄밀히 나타내면

Node<E> {
data --> E(데이터)
next --> Node<E>(다음 노드) {
		data --> E(데이터)
		next --> Node<E>(다음 노드) {
        				data --> E(데이터)
					next --> Node<E>(다음 노드)
                 }
         }
}

이렇게 되는 이유는 필드 data의 자료형인 E가 참고형이므로 클래스형 변수 data가 나타내는 것이 데이터 그 자체가 아니라 데이터를 넣어 두는 인스턴스에 대한 '참조'이기 때문이다.

 

다음 노드를 참조하는 next를 뒤쪽 포인터라 칭하자. 뒤쪽 포인터 next에 넣어 두는 것은 다음 노드에 대한 참조다. 다만 다음 노드가 없는 '꼬리 노드'의 뒤쪽 포인터값은 널을 참조한다.

 

아래는 노드의 자료형이 클래스 Node<E>형인 연결 리스트를 클래스 LinkedList<E>로 구현한 프로그램이다.

 

노드 클래스 Node<E>

노드 클래스 Node<E>는 연결 리스트 클래스 LinkedList<E> 안에 선언되어 있다. 이 클래스에는 아래와 같이 두 필드(data, next)와 생성자가 있다.

- data : 데이터(데이터 참조 : 형은 E)를 나타낸다.
- next : 뒤쪽 포인터(다음 노드 참조 : 형은 Node<E>)를 나타낸다.
- 생성자 : Node<E>의 생성자는 매개변수 data, next에 전달받은 값을 해당 필드에 대입한다.

 

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

클래스 LinkedList<E>에는 아래와 같이 두 필드가 있다.

- head : 머리 노드를 가리킨다. 머리 포인터라 하자.
- crnt : 현재 선택한 노드를 가리킨다. 리스트에서 노드를 '검색'하고 해당 노드를 선택한 후, 바로 그 노드를
         '삭제'하는 등의 용도로 사용한다. 선택 포인터라 하자.

 

생성자 LinkedList

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

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

a : 노드 0개
 
	head = null		//현재 아무런 노드도 가리키고 있지 않다.
=================================================================================
b : 노드 1개
	
    head --> A(head.next)	//머리 노드이자 꼬리 노드
=================================================================================
c : 노드 2개

	head --> A(head.next) --> B(head.next.next)

이제 노드 개수에 따라 연결 리스트를 판단하는 방법을 조금 더 살펴보자.

 

1. 연결 리스트가 비어 있는지 판단하는 방법

a는 노드가 하나도 없는 상태다(빈 연결 리스트). 이때 리스트가 비어 있는지 판단하는 방법은 아래와 같다.

head == null

 

2. 노드가 1개인 연결 리스트를 판단하는 방법

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

head가 가리키는 노드가 갖고 있는 뒤쪽 포인터값이 null이므로 연결 리스트의 노드가 1개뿐인지 판단하는 방법은 아래와 같다.

head.next == null

 

3. 노드가 2개인 연결 리스트를 판단하는 방법

c는 노드가 2개 있는 상태다. 머리 노드는 A, 꼬리 노드는 B다. 이때 head가 가리키는 노드 A의 next는 노드 B를 가리킨다. 꼬리 노드 B의 next는 null값을 갖고 있기에 연결 리스트의 노드가 2개인지 판단하는 방법은 아래와 같다.

head.next.next == null

노드 A의 데이터는 head.data이고, 노드 B의 데이터는 head.next.data이다.

 

4. 꼬리 노드인지 판단하는 방법

Node<E>형의 변수 p가 리스트의 노드 중 하나를 가리킬 때 변수 p가 가리키는 노드가 연결 리스트의 꼬리 노드인지 판단하는 방법은 아래와 같다.

p.next == null

 

검색을 수행하는 메서드 search

search 메서드는 주어진 조건을 만족하는 노드를 검색한다.

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

 

노드 스캔은 아래 조건 중 어느 하나가 성립하면 종료된다.

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

 

이 메서드가 전달받는 매개변수는 아래와 같다.

첫 번째 매개변수 obj : 검색할 때 키가 되는 데이터를 넣어 둔 객체다.
두 번째 매개변수 c : 첫 번째 매개변수와 연결 리스트의 개별 노드 안에 있는 데이터를 비교하기 위한 
                    comparator c로 obj와 선택한 노드의 데이터를 비교해 그 결과가 0이면 검색 조건이 
                    성립하는 것으로 본다.

 

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

addFirst 메서드는 리스트의 머리에 노드를 삽입한다.

 

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

addLast 메서드는 리스트 꼬리에 노드를 삽입한다. 리스트가 비어 있는지 아닌지(head == null) 먼저 확인하고 경우에 따라 아래와 같이 처리한다.

- 리스트가 비어 있는 경우 
  리스트 머리에 노드를 삽입한다. 따라서 addFirst 메서드로 처리한다.
- 리스트가 비어 있지 않은 경우
  리스트 꼬리에 노드를 삽입한다.

처리 과정은 아래와 같다.

 

1) 꼬리 노드를 찾는다. 머리 노드를 가리키도록 초기화한 ptr이 가리키는 곳은 그 뒤쪽 포인터로 업데이트하는 과정을 반복한다. 이렇게 반복하면 노드를 처음부터 차례로 스캔할 수 있다. ptr.next가 가리키는 곳이 null이 되면 while문을 종료한다. 이때 ptr이 가리키는 곳이 꼬리 노드다.

 

2) 삽입할 노드를 new Node<E>(obj, null)로 생성한다. 생성한 노드의 데이터는 obj가 되고, 뒤쪽 포인터가 가리키는 곳은 null이 된다. 이전 꼬리 노드의 뒤쪽 포인터 ptr.next가 가리키는 곳이 새로 삽입한 노드가 되도록 업데이트 한다.

 

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

removeFirst 메서드는 머리 노드를 삭제한다. 리스트가 비어 있지 않을(head != null) 때만 삭제를 실행한다.

이때 기존의 머리 노드는 실제로 없어진 것이 아니라, 그 어떤 것도 더 이상 기존의 머리 노드를 가리키지 않아 연결 리스트에서 해제된 것이다. 

 

머리 노드에 대한 참조 head에 두 번째 노드에 대한 참조 head.next를 대입해 head가 가리키는 노드를 업데이트한다.

 

리스트에 노드가 1개만 있는 경우에도 오류 없이 삭제할 수 있다. 이 경우 삭제하기 전의 머리 노드는 꼬리 노드이기에 다음 노드를 가리키는 head.next의 값은 null이다. 이 null을 head에 대입하면 리스트는 빈 상태가 된다.

 

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

removeLast 메서드는 꼬리 노드를 삭제한다. 리스트에 노드가 몇 개 있는지에 따라 아래와 같이 처리한다.

- 리스트에 노드가 1개만 있는 경우
  머리 노드를 삭제한다. 따라서 removeFirst로 처리한다.
- 리스트에 노드가 2개 이상 있는 경우
  리스트에서 꼬리 노드를 삭제한다.

처리 과정은 아래와 같다.

 

1) '꼬리 노드'와 '꼬리 노드에서 두 번째 노드'를 찾는다. 스캔은 addLast 메서드의 처리과정 1과 거의 같다. 다만 현재 스캔 중인 노드의 앞쪽 노드를 참조하는 변수 pre가 추가된 점이 다르다. while문이 종료되면 pre는 현재 꼬리 노드를, ptr은 삭제된 노드를 가리킨다.

 

2) 꼬리 노드에서 두 번째인 노드의 뒤쪽 포인터에 null을 대입한다. 그 결과 어디에서도 참조되지 않는 꼬리 노드의 메모리는 자동으로 해제된다.

 

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

remove 메서드는 임의의 노드를 삭제한다. 선택한 노드가 머리 노드인지 아닌지에 따라 아래와 같이 처리한다.

- p가 머리 노드인 경우
  머리 노드를 삭제하면 된다. 따라서 removeFirst 메서드로 처리한다.
- p가 머리 노드가 아닌 경우
  연결 리스트에서 p가 참조하는 노드를 삭제한다.

처리 과정

1) 노드 p의 바로 앞 노드를 찾는 과정이다. while문은 머리 노드에서 스캔을 시작해 선택 노드 ptr의뒤쪽 포인터인 ptr.next가 p와 같아질 때까지 반복한다. 단, 그 과정에서 null을 만나면 p가 참조하는 노드가 없다는 것이다. 이런 경우 삭제 처리를 하지 않고 return문을 실행해 메서드를 종료한다. ptr.next가 p와 같아지며 while문을 종료한다. while문이 종료된 후 ptr이 참조하는 곳은 삭제할 노드의 앞쪽 노드이다.

 

2) p가 참조하는 노드의 뒤쪽 포인터 p.next를 p의 앞쪽 노드의 포인터 ptr.next에 대입해 앞쪽 노드의 뒤쪽 포인터가 참조하는 곳을 업데이트 한다. 그 결과 어디에서도 참조하지 않는 노드(p가 참조하는 노드)의 메모리는 자동으로 해제된다.

 

선택 노드를 삭제하는 메서드 removeCurrentNode

현재 선택한 노드를 삭제하는 메서드다. remove 메서드에 선택 포인터 crnt를 건네주고 처리를 맡긴다.

 

모든 노드를 삭제하는 메서드 clear

모든 노드를 삭제하는 메서드다. 연결 리스트가 비어 있는 상태가 될 때까지 반복해 머리 요소를 삭제하여 모든 노드를 삭제한다.

 

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

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

 

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

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

 

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

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

 

아래는 각 메서드를 실행한 후 선택 포인터 crnt값이다.

 

포인터로 연결 리스트를 사용하는 프로그램 만들기

아래는 연결 리스트 LinkedList<E>를 사용하는 프로그램이다.

출력 결과

 

 

참고 서적 :