2. 연결리스트

▶ 연결리스트

차례로 연결된 노드를 표현해주는 자료구조이다.

두 가지의 형태로 나뉘는데, 단방향 연결리스트는 각 노드가 다음 노드를 가리키는 형태이며, 양방향 연결리스트에서는 각 노드는 다음노드와 이전 노드를 함께 가리킨다. 배열과 달리 연결리스트에서는 특정 인덱스를 상수 시간에 접근할 수 없다. 따라서, 배열과 같이 N번째 원소를 찾고 싶다면, 처음부터 N번 루프를 돌아야한다.

다음은 단방향 연결리스트를 구현한 코드이다.

class Node {
	Node next = null;
    public Node(int d) {
    	data = d;
    }
    
    void appendToTail(int d) {
    	Node end = new Node(d);
        Node n = this;
        whild(n.next != null) {
        	n = n.next;
        }
        n.next = end;
    }
}

 

하지만 이 코드는 LinkedList 자료구조를 사용하지 않았고, 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법을 사용했다. 이는 여러 객체들이 동시에 연결리스트를 참조하는 도중에 head가 바뀌게 되면, 어떠한 문제점이 생길 가능성이 충분히 있다. 따라서, Node클래스를 포함하는 LinkedList 클래스를 만드는 것을 선호한다. 항상, 단방향 연결리스트인지 양방향 연결리스트인지 확실하게 파악하고, 인지하고 있어야 한다.

 

▶ 단방향 연결리스트에서 노드 삭제

단방향 연결리스트의 경우에 노드 n이 주어지면, 그 이전 노드인 prev를 찾아 prev.next를 n.next와 같도록 설정한다.

양방향 연결리스트의 경우에는 n.next가 가리키는 노드를 갱신하여 n.next.prev가 n.prev와 같도록 설정해야 한다.

단방향의 경우 1, 2, 3, 4, 5의 순서로 있고 3을 제거한다고 했을 때, 이전 노드(prev)가 2고, 다음 노드(n.next)가 4이므로 prev.next를 n.next로 같게 하면 된다.

양방향의 경우 1, 2, 3, 4, 5의 순서로 있고 3을 제거한다고 했을 때, 다음 노드(n.next)인 4가 가리키는 노드를 갱신하여 n.next.prev(여기서는 3)이 n.prev(2)와 같도록 설정하게 하면 된다. 즉, 4가 가리키는 prev가 3이 아닌 2를 가리키게 하는 것이다.

이때에 중요한 것은, 첫 번째로 널 포인터 검사, 두 번째로 필요하면 head와 tail포인터도 갱신해야 한다는 점이다.

Node deleteNode(Node head, int d) {
	Node n = head;
    if(n.data == d) {
    	return head.next; /*head를 움직이는 것*/
    }
    
    while(n.next != null) {
    	if(n.next.data == d) {
        	n.next = n.next.next;
            return head; /* head는 변하지 않는다. */
        }
        n = n.next;
    }
    return head;
}

▶ Runner 기법

Runner은 부가포인터라고도 한다. 이는 연결리스트 문제에서 많이 활용되는 기법이다. 연결리스트를 순회할 때에 두 개의 포인터를 동시에 사용하는 것이다. 이때 한 포인터가 다른 포인터보다 앞서도록 한다. 앞선 포인터와 뒤에 따라오는 포인터가 서로 방향성을 가지고 이동하는 것이며, 포인터보다 항상 지정된 개수만큼을 앞서도록 할 수 있고, 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있다.

 

▶ 재귀 문제

연결리스트 관련 문제 가운데 많은 부분이 재귀 호출에 의존한다. 연결리스트 문제를 푸는 데 어려움을 겪고 있다면, 재귀적 접근법은 통할지 확인해 보아야 한다. 재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n) 만큼의 공간을 사용하고, 모든 재귀 알고리즘은 반복적인 형태로 구현될 수 있다. 하지만 반복적인 형태로 구현하면 한층 복잡해질 수도 있다.