[코딩 인터뷰]자료구조 - 연결리스트

 

👀 연결리스트

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

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

  단점 : 배열처럼 특정 인덱스를 상수 시간에 접근할 수 없습니다.

 

 

[ 연결리스트 만들기 ]

 아래의 코드에선 LinkedList 자료구조를 사용하지 않았습니다. 그리고 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법을 사용했기 때문에 여러 객체들이 동시에 연결리스트를 참조하는 도중에 head가 바뀌면 오류가 발생할 수 있습니다.

⭐ Java

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

 

 

[ 연결리스트에서 노드 삭제 ]

• 단방향 : 노드 n이 주어지면, 그 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정합니다.
• 양방향 : n.next가 가리키는 노드를 갱신하여 n.next.prev가 n.prev와 같도록 설정합니다.

❗유의할 점

    1. 널 포인터 검사를 반드시 해야 합니다.

    2. 필요하면 head와 tail 포인터도 갱신해야 합니다.

 

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

Node deleteNode(Node head, int d){
    Node n = head;
    if(n.data == d){
        return head.next;
    }
    
    while (n.next != null){
        if(n.next.data == d){
            n.next = n.next.next;
            return head;
        }
        n = n.next;
    }
    return head;
}

 

 

[ Runner 기법 ]

: 연결리스트 문제에서 많이 활용되는 기법으로 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것입니다. 한 포인터가 다른 포인터보다 앞서도록 설정합니다. 앞선 포인터가 따라오는 포인터보다 항상 지정된 개수만큼 앞서거나 여러 노드를 한 번에 뛰어넘도록 설정할 수 있습니다.

예시

 

 

[ 재귀 문제 ]

 연결리스트 관련 문제 가운데 상당수는 재귀 호출에 의존합니다. 재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘은 적어도 O(n)만큼의 공간을 사용하게 됩니다. 재귀 알고리즘은 반복적 형태로도 구현될 수 있긴 하지만 반복적 형태로 구현하면 한층 복잡해질 수 있습니다.