링크드 리스트 관련 인터뷰 질문 40가지와 답변 (2026년 기준)

작성자 : 사라 첸 사라 첸
Hours 업데이트

링크드인 관련 인터뷰 질문 및 답변 모음

자료구조 면접을 준비하려면 어려운 문제에 집중해야 합니다. 연결 리스트 관련 면접 질문은 문제 해결 능력, 포인터 논리, 메모리 활용 능력, 그리고 예외 상황에 대한 추론 방식을 보여줍니다.

연결 리스트를 완벽하게 익히면 제품 팀, 플랫폼, 시스템 엔지니어링 등 다양한 분야에서 역량을 발휘할 수 있습니다. 실무 경험을 통해 탄탄한 기술 전문성, 분석적 사고력, 깔끔한 코딩 습관을 기를 수 있습니다. 신입부터 경력직까지, 연결 리스트 기술은 실제 디버깅, 성능 분석, 후배 멘토링, 그리고 경험을 바탕으로 고급 개념을 활용하여 확장 가능한 솔루션을 개발하는 데 있어 관리자와의 협업을 지원합니다. 자세히보기 ...

👉 무료 PDF 다운로드: 연결 리스트 관련 인터뷰 질문 및 답변

링크드인 관련 인터뷰 질문 및 답변 모음

1) 연결 리스트가 무엇이며 배열과 어떻게 다른지 설명하세요.

A 연결 목록 연결 리스트는 노드라고 불리는 요소들이 포인터 또는 참조를 사용하여 연결된 선형 데이터 구조입니다. 각 노드는 데이터와 리스트에서 다음 노드를 가리키는 포인터/참조를 포함합니다. 배열과 달리 연결 리스트는 요소들을 연속적인 메모리 공간에 저장하지 않습니다.

연결 리스트와 배열의 주요 차이점:

특색 연결된 목록 배열
메모리 할당 동적 정적인
요소 접근 시간 O (N) O (1)
삽입/삭제 (어느 위치에서든) 효율적입니다. 비용이 많이 든다(이전 필요)
메모리 오버헤드 포인터용 추가 공간 포인터 오버헤드가 추가되지 않습니다.

요약하자면, 연결 리스트는 빠른 삽입과 동적 크기 조정을 제공하는 대신 임의 접근 속도가 느리고 포인터로 인해 추가적인 메모리 오버헤드가 발생합니다.

2) 연결 리스트에는 어떤 종류가 있나요?

다음의 연결 리스트의 여러 유형면접관들은 종종 그들에게 이러한 것들을 구분해 보라고 요청합니다.

  • 단일 연결 리스트: 각 노드는 다음 노드만 가리킵니다.
  • 이중 연결 목록: 노드에는 다음과 같은 것이 있습니다. 두 개의 포인터하나는 다음 노드로, 하나는 이전 노드로 이동합니다.
  • 원형 연결 리스트: 마지막 노드는 첫 번째 노드를 다시 가리키며, 루프를 형성합니다.
  • 이중 원형 연결 리스트: 원형 연결 리스트와 이중 연결 리스트를 모두 결합합니다.

각 유형은 순회 방식과 메모리 요구 사항에 따라 서로 다른 사용 사례를 가지고 있습니다. 예를 들어, 이중 연결 리스트는 추가 포인터를 사용하는 대신 역방향 순회를 쉽게 할 수 있습니다.

3) 단일 연결 리스트를 역순으로 만드는 방법은 무엇인가요? (코딩 방식)

Rev연결 리스트를 뒤집는 것은 면접에서 자주 나오는 문제입니다. 목표는 새로운 노드를 할당하지 않고 포인터의 방향을 바꿔 리스트를 제자리에서 역순으로 만드는 것입니다.

핵심 아이디어:
세 개의 포인터를 사용하세요 — prev, curr및 next — 그리고 목록을 순회합니다. 각 단계에서 리디렉션합니다. curr.next 에 prev그런 다음 모든 포인터를 앞으로 이동시키십시오.

ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev; // New head
}

이는 추가 공간 없이 연결된 구조를 변환하고 실행됩니다. O (N) 시간.

4) 연결 리스트의 중간을 찾는 두 포인터 기법에 대해 설명하시오.

연결 리스트의 중간 노드를 찾는 가장 효율적인 방법은 두 개의 포인터를 사용하는 것입니다.

  • A 느린 포인터 한 번에 한 노드씩 이동합니다.
  • A 빠른 포인터 한 번에 두 개의 노드를 이동합니다.

빠른 포인터가 끝에 도달하면 느린 포인터는 중간 지점에 있게 됩니다. 이 기술은 다음과 같은 방식으로 작동합니다. O (N) 추가 공간 없이 시간.

5) 연결 리스트에서 순환 참조를 어떻게 감지할 수 있을까요?

사이클 감지는 또 다른 고전적인 문제입니다. 표준적인 해결책은 다음과 같습니다. 플로이드의 토끼와 거북이 알고리즘:

  • 무브 slow pointer 한 번에 한 단계 씩.
  • 무브 fast pointer 한 번에 두 단계씩.
  • 리스트에 순환 구조가 있다면 두 포인터는 만나게 됩니다.

빠른 포인터가 도달하면 null리스트에는 순환이 없습니다. 이 메서드는 다음에서 실행됩니다. O (N) 시간과 O (1) 공간.

6) 연결 리스트의 장점과 단점은 무엇입니까?

연결 리스트는 몇 가지 장점과 단점을 가지고 있습니다.

장점 단점
동적 크기 무작위 접근 불가
간편한 삽입/삭제 포인터용 추가 메모리
데이터 증가에 효율적 캐시 성능 저하

연결 리스트는 동적 데이터 처리에는 성능이 좋지만, 요소 접근 시마다 헤드부터 순회해야 하므로 배열보다 속도가 느릴 수 있습니다.

관련 기사

7) 정렬된 연결 리스트 두 개를 병합하는 방법은 무엇입니까?

정렬된 두 리스트를 병합하는 것도 흔히 접하는 면접 문제 중 하나입니다. 두 리스트를 동시에 순회하면서 각 단계에서 두 리스트 중 더 작은 노드를 선택하여 새로운 정렬된 리스트를 만드는 것이 목표입니다.

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

이 방법은 정렬 순서를 유지하며 실행됩니다. O(n + m) 길이가 n과 m인 리스트를 처리하는 데 걸리는 시간.

8) 연결 리스트의 끝에서 N번째 노드를 삭제하는 방법을 설명하세요.

가장 효율적인 기술은 다음과 같습니다. 두 개의 포인터 n개의 노드로 분리되어 있습니다. 첫 번째 포인터를 n단계만큼 이동시킨 다음, 첫 번째 포인터가 끝에 도달할 때까지 두 포인터를 모두 이동합니다. 그러면 두 번째 포인터는 목표 노드 바로 앞에 위치하게 됩니다.

이렇게 하면 리스트 길이를 별도로 계산할 필요가 없으며 작업이 완료됩니다. O (N) 시간도 고려합니다. 또한 첫 번째 노드를 제거하는 것과 같은 예외적인 상황도 처리합니다.

9) 연결 리스트에서 k번째 요소에 접근하는 데 걸리는 시간 복잡도는 얼마입니까?

해당 k연결 리스트의 번째 요소를 찾으려면 헤드부터 시작하여 마지막 요소에 도달할 때까지 순회해야 합니다. kth 노드입니다. 연결 리스트는 직접적인 인덱싱을 제공하지 않기 때문에 이로 인해 비용이 발생합니다. O (N) 최악의 경우 시간.

이와 대조적으로 배열은 직접 인덱싱을 지원합니다. O (1) 시간.

10) 배열 대신 연결 리스트를 사용하는 이유는 무엇입니까?

연결 리스트는 다음과 같은 경우에 특히 유용합니다.

  • 임의의 위치에서 빈번한 삽입 및 삭제가 발생할 것으로 예상됩니다.
  • 데이터 크기를 미리 알 수 없습니다.
  • 메모리 단편화는 연속적인 메모리 할당을 어렵게 만듭니다.

이들은 효율적인 동적 메모리 할당과 리스트 끝 또는 알려진 노드 참조를 사용한 상수 시간 삽입/삭제를 지원하는데, 이는 배열이 따라올 수 없는 장점입니다.

11) 연결 리스트의 실제 응용 분야는 무엇인가요?

연결 리스트는 시스템에서 널리 사용됩니다. 동적 메모리 할당, 잦은 삽입및 가변 크기 데이터 구조 필수적입니다. 이러한 개념들은 다음과 같은 여러 핵심 컴퓨터 과학 개념 및 응용 프로그램에 구현됩니다.

  • 동적 메모리 관리 (운영체제에서 사용됨)
  • 실행 취소/다시 실행 기능 텍스트 편집기에서
  • 해시 테이블 체이닝 충돌을 해결하기 위해
  • 음악 또는 비디오 재생 목록 탐색
  • 그래프 인접성 표현
  • 다항식 연산

이 예시들은 연결 리스트가 배열 크기 조정이 비용이 많이 드는 상황에서 시퀀스를 유연하고 효율적으로 조작할 수 있도록 해준다는 점을 보여줍니다.

12) 단일 연결 리스트와 이중 연결 리스트의 차이점을 설명하세요.

특색 단일 연결 목록 이중 연결 목록
포인터 1 (다음 노드만 해당) 2 (이전 및 다음)
순회 단방향만 양방향
메모리 사용 Less (포인터는 하나뿐입니다) 추가 (추가 포인터)
삭제 더 어려움 (이전 노드 필요) 쉽게
사용 예 스택 구현 브라우저 기록 탐색

A 이중 연결 리스트 더욱 다양한 용도로 활용할 수 있지만 추가 메모리를 소모합니다. 반면에, 단일 연결 리스트 가볍고 효율적이어서 단방향 이동에 적합합니다.

13) 정렬된 연결 리스트에서 중복 항목을 제거하는 방법은 무엇입니까?

연결 리스트가 이미 정렬된 경우, 중복된 항목은 서로 인접하게 됩니다.

리스트를 순회하면서 각 노드의 데이터를 바로 다음 노드의 데이터와 비교합니다. 데이터가 일치하면 다음 노드를 건너뜁니다.

void removeDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
}

복잡성: O(n) 시간 및 O(1) 공간.

정렬되지 않은 리스트의 경우, HashSet을 사용하여 이미 확인된 값을 추적할 수 있습니다.

14) 선형 연결 리스트와 원형 연결 리스트의 차이점은 무엇입니까?

특색 선형 연결 리스트 순환 연결 목록
마지막 노드 NULL을 가리킵니다 헤드 노드를 가리킵니다
순회 언제 끝나는가 next == NULL 연속 순회
적용 사례 스택, 큐 라운드 로빈 스케줄링
복잡성 더 단순한 더 복잡한 처리

순환 리스트는 프로세스가 주기적으로 실행되는 CPU 스케줄링과 같은 응용 분야에서 특히 유용합니다.

15) 두 연결 리스트의 교점을 어떻게 찾나요?

두 개의 단일 연결 리스트가 교차하는지 확인하려면:

  1. 두 리스트의 길이를 구하세요.
  2. 더 긴 리스트의 포인터를 길이 차이만큼 이동시키세요.
  3. 두 리스트의 노드가 모두 동일해질 때까지 동시에 순회합니다.

또는 해시셋 방문한 노드를 O(n) 공간에 저장하는 데 사용할 수 있습니다.

이 접근 방식은 효율적이며 고위급 면접에서 흔히 묻는 질문입니다.

16) 두 연결 리스트가 동일한지 어떻게 확인할 수 있나요?

두 연결 리스트가 동일한 경우는 다음과 같습니다.

  • 두 시스템은 노드 수가 같습니다.
  • 해당 노드 값은 순서대로 동일합니다.

연산:

  1. 두 리스트를 동시에 순회합니다.
  2. 각 노드의 데이터를 비교하십시오.
  3. 모든 쌍이 일치하고 둘 다 NULL 값을 반환하면 두 값은 동일합니다.

시간 복잡도: O (N)

공간 복잡성: O (1)

17) 연결 리스트에서 메모리 누수란 무엇인가요?

A 메모리 누출 동적으로 할당된 노드가 사용 후 해제되지 않을 때 발생합니다.

연결 리스트에서, 만약 delete or free() 목록에서 제거된 노드에 대해서는 해당 메서드가 호출되지 않으므로, 더 이상 접근할 수 없더라도 메모리는 계속 점유된 상태로 남아 있습니다.

예를 들어, C/에서 삭제된 노드를 해제하지 못하는 경우C++ 이는 점진적인 메모리 고갈로 이어져 시스템 속도 저하 또는 충돌을 유발합니다.

소멸자를 사용하거나 명시적으로 메모리 할당을 해제하는 등 적절한 정리 작업을 수행하면 이 문제를 방지할 수 있습니다.

18) 연결 리스트를 이용하여 스택을 구현하는 방법을 설명하시오.

안에 스택요소들은 LIFO(후입선출) 순서를 따릅니다.

연결 리스트는 삽입과 삭제가 헤드에서 효율적으로 이루어지기 때문에 이상적입니다.

Operations :

  • 푸시: 헤드에 새 노드를 삽입합니다.
  • 팝: 헤드에서 노드를 제거합니다.
  • 몰래 엿보다: 헤드 데이터를 반환합니다.

장점:
고정 크기 배열이 필요 없습니다. 요소가 추가될 때마다 배열 크기가 동적으로 커집니다.

19) 연결 리스트를 이용하여 큐를 구현하는 방법은 무엇입니까?

안에 변발요소들은 FIFO(선입선출) 순서를 따릅니다.

다음과 같은 경우 연결 리스트를 사용하세요:

  • 대기열에 추가(삽입): 끝에 노드를 추가합니다.
  • 대기열에서 제거(삭제): 헤드에서 노드를 삭제합니다.

이를 통해 두 가지 작업 모두 가능합니다. O (1) 두 개의 포인터로 시간을 보내세요 — front 및 rear.

이는 일반적으로 공정 스케줄링 및 프린터 대기열 시스템에 사용됩니다.

20) 배열 리스트와 연결 리스트의 차이점은 무엇인가요? Java?

아래 ArrayList 연결 목록
스토리지 동적 배열 이중 연결 리스트
액세스 시간 O (1) O (N)
삽입/삭제 중부 지역이 비쌈 끝부분이 효율적입니다
메모리 오버헤드 Less 추가 정보 (더 보기)
적용 사례 자주 접근 잦은 삽입/삭제

예: ArrayList 조회 작업이 많은 경우, 그리고 LinkedList 삽입/삭제 작업이 주를 이룰 때.

21) 다단계 연결 리스트를 어떻게 평면화하나요?

A 다단계 연결 리스트 두 가지 특징을 모두 가진 노드를 포함할 수 있습니다. next 및 child 포인터(각 자식은 다른 연결 리스트로 연결됨). 목표는 모든 노드를 단일 레벨 연결 리스트로 평면화하는 것입니다.

접근:

  1. 사용하십시오 스택 or 재귀 함수.
  2. 헤드 노드부터 시작하세요.
  3. 노드에 다음과 같은 것이 있는 경우 child밀어붙여라 next 스택에 노드를 추가하고 만드세요 child as next.
  4. 스택이 비어 있을 때까지 계속합니다.

시간 복잡성 : O (N)

공간 복잡성 : 재귀/스택의 경우 O(n)입니다.

예시 (개념적):

1 - 2 - 3
    |
    4 - 5
Flattened → 1 → 2 → 4 → 5 → 3

이 문제는 재귀와 포인터 조작에 대한 이해도를 평가합니다.

22) 임의의 포인터를 사용하여 연결 리스트를 복제하는 방법은 무엇입니까?

이 특수한 연결 리스트의 각 노드에는 두 개의 포인터가 있습니다.

  • next → 다음 노드를 가리킵니다.
  • random → 임의의 노드를 가리킵니다.

알고리즘 (3단계):

  1. 원본 노드 사이에 복제된 노드를 삽입합니다.
  2. 클론에 임의의 포인터를 할당합니다.clone.random = original.random.next).
  3. 두 목록을 분리하세요.

이렇게 하면 해시맵을 위한 추가 공간을 확보할 필요가 없고 실행 시간도 단축됩니다. O (N) ~와 시간 O (1) 추가 공간.

사용 사례 : 그래프나 객체 참조와 같은 복잡한 데이터 구조를 깊이 복사하는 기능.

23) 스킵 리스트란 무엇이며, 연결 리스트와는 어떤 관계가 있습니까?

A 건너뛰기 목록 계층형 연결 리스트 구조로, 빠른 검색, 삽입 및 삭제가 가능합니다(균형 트리와 유사).

Opera기 평균 시간 최악의 경우
검색 O (로그 n) O (N)
삽입/삭제 O (로그 n) O (N)

이 시스템은 여러 단계로 구성되어 있으며, 상위 단계에서는 여러 노드를 "건너뛰어" 검색 효율성을 향상시킵니다.

예: Redis와 같은 데이터베이스 및 동시 맵 구현에서 사용됩니다.

24) 연결 리스트에서 회문을 어떻게 찾을 수 있습니까?

연결 리스트는 앞뒤로 읽었을 때 내용이 동일하면 회문입니다.

연산:

  1. 목록의 중간을 찾으세요.
  2. Rev후반전을 건너뛰세요.
  3. 두 부분을 노드별로 비교하세요.

대응하는 모든 노드가 일치하면 회문입니다.

예:

1 → 2 → 3 → 2 → 1 → ✅ 회문

1 → 2 → 3 → 4 → ❌ 회문이 아닙니다

시간 복잡성 : O (N)

공간 복잡성 : O (1)

25) 연결 리스트에서 반복문을 어떻게 제거하나요?

플로이드의 주기 감지 방법을 사용하여 루프가 존재하는 경우, 다음 단계를 따라 루프를 제거하십시오.

  1. 느린 포인터와 빠른 포인터의 교차점을 감지합니다.
  2. 포인터 하나를 머리 쪽으로 옮기세요.
  3. 두 포인터를 한 단계씩 움직여서 한 지점에서 만날 때까지 이동시키세요. 루프 시작 노드.
  4. 이전 노드를 설정합니다. next 에 null.

이 접근 방식은 사이클을 해결하는 동안 추가적인 메모리 사용을 방지합니다.

26) 메모리에서 연결 리스트를 표현하는 다양한 방법에는 무엇이 있습니까?

연결 리스트는 다음과 같이 표현할 수 있습니다. 세 가지 주요 방법:

표현 유형 기술설명 사용 예
동적 노드 각 노드는 동적으로 할당되고 연결됩니다. C, C++
정적 배열 표현 포인터 대신 배열 인덱스를 사용합니다. 임베디드 시스템
연결된 개체 클래스를 이용한 객체지향 표현 Java, Python

각 접근 방식은 서로 다른 환경에 적합합니다. 예를 들어, 배열 기반 목록은 포인터 조작이 제한될 때 사용됩니다.

27) 연결 리스트의 길이를 어떻게 구할 수 있습니까? (반복적 방법과 재귀적 방법 모두 사용 가능)

반복적 접근 방식:

int getLength(ListNode head) {
    int count = 0;
    while (head != null) {
        count++;
        head = head.next;
    }
    return count;
}

재귀적 접근 방식:

int getLength(ListNode head) {
    if (head == null) return 0;
    return 1 + getLength(head.next);
}

두 접근 방식 모두 O (N) 시간 복잡도; 재귀 호출은 추가 기능을 제공합니다. O (N) 호출 스택으로 인한 공간 오버헤드.

28) 원형 이중 연결 리스트의 개념을 예시와 함께 설명하시오.

안에 원형 이중 연결 리스트각 노드는 다음 노드로 가는 링크 하나와 이전 노드로 가는 링크 하나, 이렇게 두 개의 링크를 가지고 있으며, 마지막 노드의 next 머리를 가리키는 반면, 머리는 prev 마지막 노드를 가리킵니다.

사용 사례 예시:

  • 실시간 운영 체제(라운드 로빈 스케줄링)
  • 음악 재생 목록 반복 재생
  • 탭 또는 슬라이드 간 탐색

장점:

  • 양방향 순회.
  • 널 참조가 없습니다.
  • 효율적인 삽입 및 삭제.

29) 연결 리스트에서 홀수 번째 노드를 삭제하는 방법은 무엇입니까?

연산:

  1. 머리부터 시작하세요.
  2. 포인터를 조정하여 두 번째 노드마다 삭제합니다.
  3. 목록이 끝날 때까지 계속하세요.

예:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 3 → 5

복잡성:

  • 시간 복잡도: O(n)
  • 공간: O(1)

이는 포인터 순회 및 삭제 안전성에 대한 이해도를 확인하는 것입니다.

30) 연결 리스트의 시작과 끝에서 n번째 노드를 어떻게 찾을 수 있습니까?

처음부터: count가 n이 될 때까지 리스트를 순회합니다.

끝에서부터: 포인터 두 개를 사용하세요.

  1. 첫 번째 포인터를 n단계 앞으로 이동합니다.
  2. 첫 번째 값이 0이 될 때까지 두 값을 동시에 이동시키세요.
  3. 두 번째 포인터는 이제 끝에서 n번째 노드를 가리킵니다.

시간 복잡성 : O (N)

공간 복잡성 : O (1)

이 접근 방식은 길이를 별도로 계산하는 것을 방지하여 효율성을 향상시킵니다.

31) 연결 리스트의 순서를 어떻게 바꾸나요?

문제: 주어진 리스트 L0 → L1 → … → Ln-1 → Ln순서를 바꿔주세요 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

단계 :

  1. 목록의 중간을 찾으세요.
  2. Rev후반전을 건너뛰세요.
  3. 두 부분을 번갈아 가며 합치세요.

예:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 5 → 2 → 4 → 3

복잡성: 시간은 O(n), 공간은 O(1)입니다.

이 문제는 하나의 문제에서 여러 연결 리스트 연산을 테스트합니다.

32) 주어진 값 x를 기준으로 연결 리스트를 어떻게 분할합니까?

목표:
x보다 작은 모든 노드가 x보다 크거나 같은 노드보다 앞에 오도록 노드를 재배열하십시오.

접근:

  • 두 개의 더미 목록을 유지하세요: before 및 after.
  • 원본 리스트를 순회하고 각 리스트에 노드를 추가합니다.
  • 마지막에 모두 합치세요.

예:

Input: 3 → 5 → 8 → 5 → 10 → 2 → 1, x = 5  
Output: 3 → 2 → 1 → 5 → 8 → 5 → 10

이는 데이터 재배열 능력을 평가하기 위해 자주 요구되는 사항입니다.

33) 연결 리스트를 정렬하는 방법은 무엇입니까?

연결 리스트는 임의 접근을 지원하지 않으므로, 정렬 병합 최고의 선택입니다.

단계 :

  1. 느린 포인터와 빠른 포인터를 사용하여 목록을 절반으로 나눕니다.
  2. 각 절반을 재귀적으로 정렬합니다.
  3. 정렬된 절반을 병합합니다.

장점:

  • O(n log n) 시간.
  • O(1) 추가 공간(반복 버전용).

배열과 달리, 퀵 정렬은 포인터 재배열의 복잡성 때문에 연결 리스트에 대해서는 비효율적입니다.

34) 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트의 차이점은 무엇입니까?

특색 하나씩 두배로 원형의
링크 하나(다음) 두 개 (이전 & 다음) 마지막 노드가 헤드에 연결됩니다.
순회 앞으로 만 앞뒤로 무한 이동 가능
삽입/삭제 보통 양쪽 모두 더 쉽습니다 특수 사례 처리
적용 사례 스택, 큐 실행 취소 라운드 로빈 스케줄링

이 비교 질문은 개념의 명확성을 확인하기 위해 자주 사용됩니다.

35) 두 개의 원형 연결 리스트의 교차 노드를 어떻게 찾습니까?

이는 교차 문제의 확장입니다.

연산:

  1. 각 리스트에 루프가 있는지 감지합니다.
  2. 두 교차점이 모두 비순환적이라면 표준 교차점 알고리즘을 사용합니다.
  3. 두 루프 모두 순환 루프인 경우 → 각 루프의 시작점을 찾아 동일하거나 연결되어 있는지 확인합니다.

이 문제는 여러 가지를 결합한 것입니다. 사이클 감지 및 교차 논리다중 개념 추론을 테스트합니다.

36) 정렬된 연결 리스트에 노드를 삽입하는 방법을 설명하세요.

단계 :

  1. 주어진 값으로 새 노드를 생성합니다.
  2. 정확한 위치를 찾을 때까지 이동하세요.
  3. 조정 next 그에 따라 포인터를 사용하세요.

예:

Input: 1 → 3 → 5 → 7, Insert 4  
Output: 1 → 3 → 4 → 5 → 7

이는 포인터 조정에 대한 이해도를 테스트하기 위한 기본적인 조작 문제입니다.

37) 연결 리스트를 두 부분으로 나누는 방법은 무엇입니까?

연산:

  • 느린 포인터와 빠른 포인터 방법을 사용하십시오.
  • 인셀덤 공식 판매점인 fast 끝에 다다르면, slow 중간 지점에 있을 것입니다.
  • 해당 노드에서 분할합니다.

예:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 2 → 3  and  4 → 5

이 연산은 연결 리스트 병합 정렬의 첫 번째 단계인 경우가 많습니다.

38) 연결 리스트에서 특정 값의 마지막 발생 위치를 어떻게 찾습니까?

리스트를 순회하면서 목표값이 발견된 마지막 노드를 추적합니다.

의사 코드:

ListNode findLastOccurrence(ListNode head, int val) {
    ListNode result = null;
    while (head != null) {
        if (head.val == val) result = head;
        head = head.next;
    }
    return result;
}

복잡성: O (N)

이는 순회 및 조건 검사에 대한 이해도를 확인하는 것입니다.

39) 연결 리스트에서 특정 키가 포함된 모든 항목을 제거하려면 어떻게 해야 합니까?

연산:

  1. 대상 키를 포함하는 경우 헤드 노드를 먼저 처리합니다.
  2. 그다음에는 해당 키를 포함하는 후속 노드들을 순회하며 삭제합니다.

예:

Input: 1 → 2 → 6 → 3 → 4 → 5 → 6, Key = 6  
Output: 1 → 2 → 3 → 4 → 5

복잡성: O (N)

이는 예외적인 경우(특히 헤드 삭제)에 대한 지식을 보여줍니다.

40) 스택과 연결 리스트 데이터 구조의 주요 차이점은 무엇입니까?

특색 스택 연결된 목록
접근 유형 LIFO(후입선출) 순차
실시 배열 또는 연결 리스트 노드 기반
행정부 푸시/팝 삽입/삭제/탐색
유연성 제한된 액세스 유연한 접근
적용 사례 함수 호출 관리 동적 데이터 처리

스택은 구현될 수 있습니다. 연결 리스트를 사용하여하지만 개념적으로는 차이가 있습니다. 스택은 접근이 제한된 반면, 연결 리스트는 범용 구조입니다.

🔍 실제 시나리오 및 전략적 대응 방안을 포함한 링크드인 리스트 인터뷰 주요 질문

1) 연결 리스트란 무엇이며, 배열과는 어떻게 다른가요?

후보자에게 기대하는 것: 면접관은 지원자가 기본적인 데이터 구조를 얼마나 잘 이해하고 있는지, 그리고 여러 옵션 간의 장단점을 비교하는 능력을 평가하고자 합니다.

예시 답변: 연결 리스트는 노드라고 불리는 요소들이 포인터로 연결된 선형 데이터 구조입니다. 각 노드는 데이터와 다음 노드에 대한 참조를 포함합니다. 배열과 달리 연결 리스트는 연속적인 메모리 공간을 필요로 하지 않고 동적으로 크기를 조정할 수 있지만, 요소에 대한 인덱싱이 없기 때문에 접근 속도가 느립니다.

2) 실제 응용 프로그램에서 배열 대신 연결 리스트를 선택하는 경우는 언제입니까?

후보자에게 기대하는 것: 그들은 적절한 데이터 구조를 선택하는 데 있어서 당신의 실질적인 판단력을 평가하고 있습니다.

예시 답변: 데이터셋 중간 부분에서 빈번한 삽입 및 삭제가 필요한 경우 연결 리스트를 선택하겠습니다. 이전 직장에서 작업 스케줄링 기능을 개발했는데, 작업이 자주 추가되고 삭제되는 상황에서 연결 리스트가 배열보다 더 나은 성능을 보여주었습니다.

3) 단일 연결 리스트와 이중 연결 리스트의 차이점을 설명해 주시겠습니까?

후보자에게 기대하는 것: 면접관은 지원자의 개념 이해도와 기술적 차이점을 명확하게 설명하는 능력을 확인하고자 합니다.

예시 답변: 단일 연결 리스트는 노드가 바로 다음 노드만 가리키는 반면, 이중 연결 리스트는 노드가 바로 다음 노드와 이전 노드 모두를 가리킵니다. 이중 연결 리스트는 역방향 탐색이 더 쉽지만, 추가적인 포인터 때문에 더 많은 메모리를 필요로 합니다.

4) 연결 리스트에서 순환을 어떻게 감지할 수 있나요?

후보자에게 기대하는 것: 이 문제는 문제 해결 능력과 일반적인 알고리즘 패턴에 대한 이해도를 평가합니다.

예시 답변: 흔히 사용되는 방법 중 하나는 서로 다른 속도로 움직이는 두 개의 포인터를 이용하는 것인데, 이를 '느린 포인터와 빠른 포인터' 기법이라고 합니다. 무한 루프가 발생할 경우, 두 포인터는 결국 만나게 됩니다. 저는 이전 직장에서 데이터 처리 파이프라인의 무한 루프를 방지하기 위해 이 방법을 사용한 적이 있습니다.

5) 연결 리스트에서 일반적으로 수행되는 연산에는 어떤 것들이 있습니까?

후보자에게 기대하는 것: 면접관은 지원자가 표준 운영 절차와 그 의미를 이해하고 있는지 확인하고 싶어합니다.

예시 답변: 일반적인 연산에는 삽입, 삭제, 순회, 검색 및 리스트 역순 정렬이 있습니다. 각 연산은 수행 위치에 따라 시간 복잡도가 다르며, 이는 효율적인 시스템을 설계할 때 중요한 요소입니다.

6) 연결 리스트 중간에 노드를 삽입하는 것은 어떻게 처리하나요?

후보자에게 기대하는 것: 그들은 당신이 포인터 조작을 얼마나 잘 이해하고 있는지, 그리고 세부 사항에 얼마나 주의를 기울이는지 확인하고 있습니다.

예시 답변: 중간에 노드를 삽입하려면 먼저 리스트를 순회하여 목표 위치를 찾은 다음, 새 노드가 다음 노드를 가리키고 이전 노드가 새 노드를 가리키도록 포인터를 조정합니다. 리스트가 손상되지 않도록 포인터를 신중하게 업데이트하는 것이 매우 중요합니다.

7) 연결 리스트로 인해 성능 문제가 발생했던 상황과 그 해결 방법을 설명하십시오.

후보자에게 기대하는 것: 이 행동 관련 질문은 당신의 반성 및 최적화 능력을 평가합니다.

예시 답변: 이전 직장에서는 빈번한 검색 작업에 연결 리스트를 사용했는데, 이로 인해 성능이 저하되었습니다. 저는 이 문제를 파악하고 해시 기반 구조로 전환할 것을 제안했고, 그 결과 검색 속도가 크게 향상되었습니다.

8) 연결 리스트를 역순으로 만들려면 어떻게 해야 할까요?

후보자에게 기대하는 것: 면접관은 당신의 논리적 사고력과 반복적 또는 재귀적 접근 방식에 대한 이해도를 테스트하고 있습니다.

예시 답변: 연결 리스트를 역순으로 만들려면, 리스트를 순회하면서 각 노드의 `next` 포인터가 이전 노드를 가리키도록 변경하면 됩니다. 이 과정은 모든 포인터가 역순으로 바뀌고 헤드가 업데이트될 때까지 계속됩니다.

9) 연결 리스트를 사용하는 장점과 단점은 무엇입니까?

후보자에게 기대하는 것: 그들은 균형 잡힌 시각과 장단점에 대한 인식을 원합니다.

예시 답변: 장점으로는 동적 크기 조절과 효율적인 삽입 및 삭제가 있습니다. 단점으로는 배열에 비해 메모리 사용량이 많고 접근 속도가 느리다는 점이 있습니다. 이전 직무에서 이러한 장단점을 이해하는 것은 다양한 구성 요소에 적합한 구조를 선택하는 데 도움이 되었습니다.

10) 시스템 설계에서 어떤 유형의 연결 리스트를 사용할지 어떻게 결정하나요?

후보자에게 기대하는 것: 이 상황 질문은 건축적 맥락에서의 의사결정을 평가합니다.

예시 답변: 저는 순회 요구 사항, 메모리 제약 조건, 연산 빈도와 같은 요소를 고려합니다. 예를 들어, 역방향 순회가 필요한 경우에는 이중 연결 리스트가 더 적합하지만, 더 간단하고 메모리 효율적인 구현에는 단일 연결 리스트로도 충분합니다.

이 게시물을 요약하면 다음과 같습니다.