[자료구조] 연결리스트

최근 CS 기술 면접 대비에 시간을 많이 쓰고 있다.
여러 자료 + 이전 강의에서 본 내용을 보면서 GPT와 모의면접을 하고 있는데, 생각보다 시간이 엄청 쓰인다.

이렇게 시간을 많이 쓰는데 면접이 끝나고, 붙으면 좋겠지만 혹여 떨어지면 지금 준비하는 이 시간이 아무것도 안한 시간이 될까봐. 
그리고 분명히 작년 11월 즈음 면접 준비를 하긴 했는데, 기억에서 날라가버렸다..
뭐라도 남겨보자는 심정과 노션에 흩어진 글을 조금이라도 정제해보자는 마음으로 이 포스팅을 시작하였다.

주로 GPT + VSFe 님의 기술면접 질문 모음집을 참고하였다.
질문과 답변 모두 신입 개발자의 입장에서 쓰여진 것이니 오류나 말이 안 맞는 것이 있을 수 있다. 혹은 더 좋은 답변이 있을 수 있다.
이를 발견하여 제게 알려주신다면 커피..라도 한잔 사드리고 싶을 것 같다. 🙇🏻‍♂️

링크드 리스트에 대해 설명해 주세요.

링크드리스트는 각 노드들이 있고, 이들이 포인터로 연결된 선형 자료구조입니다.

보통 데이터, next를 포함하고, 인덱스가 아닌 순차적으로 포인터를 통해 접근해야합니다.

종류로는 한방향, 이중연결, 원형 연결 리스트가 있습니다.

탐색에는 O(n)이 걸리지만, 맨앞 삽입/삭제는 O(1), 중간과 끝은 O(n)이 걸립니다.

동적 메모리 할당이 유연하지만 임의 접근이 불가능해 탐색해야합니다.

왜 맨앞 추가/삭제는 O(1)인가?

새 노드의 next를 head로 연결해주면 됩니다.

만약 tail을 알면 맨뒤 추가도 O(1)입니다.

하지만 단일 연결리스트라면, tail을 삭제할 때, tail 이전 노드를 모르기에 O(n)입니다.

이중 연결리스트라면 tail 삭제는 O(1)입니다.

큐, 스택 구현에 배열보다 유리한가?

스택의 경우, 기본 연산이 push, pop인데,

배열로 구현하면, 맨 뒤에 push, pop에 O(1)입니다.

메모리 접근 측면에서는 캐시 효율이 올라갈 수 있습니다. 다만 배열 크기 초과시, 재할당 비용이 O(n)입니다.

연결리스트의 경우

head에 추가/삭제하면 O(1)입니다. 크기의 제한이 없어 유연하지만, 메모리가 분산되어 캐시 효율이 떨어질 수 있습니다.

스택에는 배열이 더 유리할 수 있습니다.

큐의 경우, 기본 연산이 뒤에서 추가, 앞에서 삭제 합니다.

배열로 구현 시, 앞에서 삭제한 후, 몯느 요소를 한 칸씩 당기는 shift 연산이 O(n)입니다.

만약 이를 극복하려면 순환 큐로 구현해야 O(1)입니다.

연결리스트로 구현 시, head에서 삭제, tail에서 추가하여 O(1) 입니다.

큐에는 연결리스트가 더 유리할 수 있습니다.

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedQueue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  enqueue(val) {
    const newNode = new Node(val);
    if (this.tail) this.tail.next = newNode;
    else this.head = newNode;
    this.tail = newNode;
  }

  dequeue() {
    if (!this.head) return null;
    const val = this.head.val;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    return val;
  }
}

 

자바스크립트에서 배열로 큐를 구현하면 shift가 느리다. 어떻게 개선할 수 있을까?

배열 하나로 shift 하지 말고 배열 두개로 큐를 구현합니다.

하나의 배열은 inStack으로 push를 하는 enqueue 스택입니다.

나머지 하나는 outStack으로 pop을 하는 dequeue 스택입니다.

예를 들어, enqueue를 하면, 값을 inStack에 push합니다.

이후 Push는 계속 inStack에 push 하다가, dequeue 명령어가 오면, 두가지 행동으로 나뉩니다.

1. 먼저 outStack이 비어있으면, inStack의 모든 요소를 pop하여 outStack에 push합니다.
2. outStack이 비어있지 않으면 outStack에서 pop만 하면 됩니다.

dequeue시, outStack을 채워주는 행위는 stack의 순서를 뒤집는 것입니다.

이것이 효율적인 이유는, pop, push 연산은 O(1)이기 때문입니다.

하지만 inStack → outStack으로 가는 작업이 O(n)이지 않냐는 의문이 들 수 있습니다.

여기서 생각해볼 수 있는 개념은 amortized O(1)이라고 부릅니다. 한국어로는 분할상환 분석이라고 합니다.

전체 n개의 input에서, 평균적으로 각 연산은 O(1)입니다.

만약 outStack이 비었을때만 inStack에서 옮겨지는 연산을 수행하지만, 각 원소는 최대 한번만 옮겨지는 행위를 당하게됩니다.

대부분의 연산은 O(1)이지만, 가끔 일어나는 O(n) 때문에 모든 연산이 O(n)이라고 할 수는 없고, 대부분의 O(1)연산에 가끔 한번씩 일어나는 O(n)의 오버헤드를 분할해 O(n)을 줄인다는 개념입니다.

https://gazelle-and-cs.tistory.com/87

각각 언제 유리한가?

배열이 유리한 경우는 다음과 같습니다.

• 데이터 크기가 고정되거나 예측될때
• 인덱스를 통한 빠른 접근이 중요할 때,
• 읽기 작업이 많으면 메모리 연속성 때문에 캐시 효율이 좋음
• 정렬, 탐색 등 순차 알고리즘 사용 시 연산 최적화가 쉽다(sort, binary search 등)
• 포인터 저장을 안해서 메모리 오버헤드가 줄어듦

연결리스트는 다음과 같습니다.

• 데이터 크기가 계속 동적으로 바뀔 때
• 중간 삽입 삭제가 자주 일어날 때 (단 위치를 알아야 포인터만 조작하므로 O(1))
• 맨 앞의 삽입 삭제가 빈번할 때(배열은 shift O(n))
• 큐, 스택 자료구조 구현시

배열 데이터 크기를 모든 언어에서 고정적으로 선언해야하나?

JS나 파이썬은 동적 배열을 사용해서, 내부적으로 리사이징한다.

즉, 배열 사이즈를 넘기면, 더 큰 배열을 새로 만들어서 기존 요소를 복사한다.

이 과정은 O(n)이지만, 자주일어나지 않아서 amortized O(1)이라고 한다.

중간과 끝 삽입삭제를 개선할 방법이 있을까?

1. 이중연결리스트라면, prev와 tail 포인터를 사용해 끝에서 삭제를 O(1)으로 만들 수 있다.
2. Skip List (링크드 + 건너뛰기 포인터)
   “정렬된 링크드리스트” 에서, 여러 레벨을 두고, 만약 현재 위치의 다음 element가 탐색하려는 값보다 크면 점점 아래로 내려갑니다. 이분탐색과 비슷합니다.
   https://hoororyn.tistory.com/14

 

3. 해시맵 + 링크드리스트
해시맵으로 검색은 O(1)이고, 이중 연결리스트로 순서를 관리한다. head, tail 삽입 삭제는 O(1)

 

4. Unrolled Linked list (배열+링크드)
각 노드에 값이 아닌 배열을 저장하는 구조
중간 접근을 빠르게, 메모리 효율도 개선(하나의 노드에 여러 요소를 저장해 캐시 효율 업)
삽입 삭제가 O(√n)

텍스트 에디터(줄편집)에서 사용

 

일반 배열과, 링크드 리스트를 비교해 주세요.

일반 배열은 보통 미리 크기를 지정하지만, 링크드 리스트는 동적으로 확장 가능합니다. (왜? 언어마다 다르지 않나)

배열은 인덱스로 바로 접근 가능하지만, 링크드리스트는 순차 탐색을 해야한다.

배열은 중간 삽입/삭제 비용이 크지만, 링크드리스트는 포인터 조작하면 된다.

링크드 리스트를 사용해서 구현할 수 있는 다른 자료구조에 대해 설명해 주세요.

스택 : head를 top으로 구현 → 브라우저 히스토리

큐 : head, tail로 구현 → 작업대기열, 이벤트 처리

이중 연결리스트 : 각 노드가 next, prev를 가지며, 양방향 순회. → LRU Cache

Deque: 앞 뒤 양쪽에서 삽입 삭제 가능, 이중 연결리스트로 구현, pushFront/pushBack, popFront, popBack 모두 O(1) → 브라우저 탭 순환, undo/redo

해시테이블 충돌 해결 : 검색 최악은 O(n)

그래프 인접 리스트 표현 : 각 정점에 연결된 정점 리스트를 저장, 인접 행렬보다 메모리 효율 좋음

폴더 트리, 트라이(Trie) 등 계층 구조 : 노드에 자식 포인터를 붙임 → 문자열 검색, 자동 완성 시스템

단일 연결 리스트에서 뒤에서 k번째 노드를 찾는 방법은?

투포인터로 fast, slow 를 구현한다.

먼저 k만큼 fast를 이동시킨 후, fast와 slow를 한칸씩 탐색한다.

fast가 끝에 도달하면 slow는 뒤에서 k번째일 것이다.

아이디어는 fast와 slow의 간격을 k만큼 유지시키는 것

단일 연결리스트에서 중간 노드를 찾는 방법은?

이 또한 투 포인터로 fast는 한번에 두 칸 이동, slow는 한번에 1칸 이동한다.

단일 연결리스트에서 사이클 찾기

플로이드의 토끼와 거북이

https://fierycoding.tistory.com/45

 

인덱스와 링크드리스트를 합친 개념은 없는가?

• 링크드 리스트 기반이지만, 중간중간에 빠른 접근을 위한 “다단계 인덱스”를 둔 구조.
  마치 계단처럼 여러 층의 링크드 리스트가 있고,
  높은 레벨일수록 더 많은 노드를 건너뛰며 검색 가능
  정렬된 데이터 유지
  검색, 삽입, 삭제 모두 O(log n) 성능
  동적 구조 → 트리처럼 재구성 필요 없음
  Redis의 Sorted Set 내부 구현이 skip list