[코딩 인터뷰 완전 분석] 자료구조 / 연결리스트

연결리스트의 정의

• 차례로 연결된 노드를 표현해주는 자료구조.
• 단방향 연결리스트에서 각 노드는 다음 노드를 가리킨다.
• 양방향 연결리스트에서 각 노드는 다음 노드와 이전 노드를 가리킨다.

배열과는 달리, 특정 인덱스를 상수 시간에 접근할 수 없다. 리스트에서 k번째 원소를 찾고 싶다면, 처음부터 k번 루프를 돌아야 한다.

단방향 연결리스트의 예 

한 노드는 [데이터 + 다른 노드를 가리키는 포인터]로 이루어져 있다. 처음 시작하는 노드는 head 노드인데, 단일 연결리스트를 구현하는 데 필수적이다. 맨 처음 노드(위에서 data 3을 가지고 있는 노드)의 주소를 담기 위해서 head를 사용한다.

 

연결리스트의 장점 : 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다.

 

연결리스트의 구현

기본적인 단방향 연결리스트 구현

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

위의 코드에서는, LinkedList 자료구조를 사용하지 않고, 연결리스트에 접근할 때 head노드의 주소를 참조하는 방법을 사용하였다. 이 때, 여러 객체들이 동시에 연결리스트를 참조하는 도중에 head가 바뀐다면, 어떤 객체들은 이전 head를 계속 가리키고 있을 수도 있다.

 

할 수 있다면, Node 클래스를 포함하는 LinkedList클래스를 만드는 게 좋다. 

이런 식으로 한다면, 해당 클래스 안에 head Node 변수를 단 하나만 정의해 놓음으로써 위 문제점을 완전히 해결한다.

 

면접에서, 단방향 연결리스트인지 양방향 연결리스트인지 반드시 인지하고 있어야 한다!

 

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

삭제할 노드 n이 주어지면 그 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정한다. 

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

유의할 점

• 널 포인트 검사를 해야 한다.
• head와 tail 포인터도 갱신해줘야 한다.
• C나 C++처럼 메모리 관리가 필요한 언어를 사용해 구현하는 경우에는, 삭제한 노드에 할당한 메모리가 제대로 반환되었는지 반드시 확인해줘야 함.

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 (부가 포인터 라고도 함)는 연결리스트 문제에서 많이 활용되는 기법이다.

연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것이다. 이때 한 포인터가 다른 포인터보다 앞서도록 한다. 

앞선 포인터가 따라오는 포인터보다 항상 지정된 개수만큼을 앞서도록 할 수도 있고, 아니면 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있다.

 

예를 들어, 연결리스트 a1->a2->...->an->b1->b2->...->bn이 있다고 하자.

이 연결리스트를 a1->b1->a2->b2->...->an->bn과 같이 재정렬하고 싶다고 한다. 연결리스트의 정확한 길이는 모르지만, 길이는 짝수라는 정보가 주어졌다.

 

-> 이때, 포인터 p1(앞선 포인터)를 두고, 따라오는 포인터 p2가 한 번 움직일 때마다 포인터 p1이 두 번 움직이도록 설정해 보자. 그랬을 때 p1이 연결리스트 끝에 도달하면 p2는 가운데 지점에 있게 될 것이다. 이 상태에서 p1을 다시 맨 앞으로 옮긴 다음 p2로 하여금 원소를 재배열하도록 만들 수 있다. 즉, 루프가 실행될 때마다 p2가 가리키는 원소를 p1뒤로 옮기는 것이다. 

 

재귀 문제

대부분의 연결리스트 문제는 재귀 문제이다. 재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n)만큼의 공간을 사용한다는 사실을 기억하자. 모든 재귀 알고리즘은 반복적 형태로도 구현될 수있긴 하지만 반복적 형태로 구현하면 한층 복잡해질 것이다.