단방향 연결 리스트: head·tail 삽입과 삭제

1. 번호 대신 “다음은 누구인가”를 적습니다

곡 A를 듣고 나면 B, B 다음에는 C를 들을 재생 목록을 생각해 보세요. 배열은 0번, 1번, 2번 같은 위치로 곡을 읽습니다. 연결 리스트는 각 항목에 “내 값”과 “다음 항목”을 함께 적어 둡니다. 시작 항목을 알면 다음 표시를 따라 목록을 읽을 수 있습니다.

항목	내 값	다음 항목
첫 항목	A	B 항목
두 번째 항목	B	C 항목
마지막 항목	C	없음(null)

이를 A → B → C → null이라고 줄여 쓰겠습니다. 화살표는 곡이 이동한다는 뜻이 아니라 “다음에 이 항목으로 간다”는 연결입니다. 이런 항목 하나를 노드(node)라고 부릅니다. 처음에는 “값과 다음 표시가 든 작은 객체”라고 이해하면 충분합니다.

2. JavaScript 객체 두 개를 먼저 연결합니다

이 글의 예제는 브라우저 개발자 도구 Console 탭에서 실행할 수 있습니다. 파일 저장이나 설치 없이 각 코드 블록 전체를 붙여 넣으세요. 각 예제는 다른 예제 없이도 실행됩니다. 같은 예제를 다시 실행하다 이름이 이미 선언되었다는 오류가 나오면 페이지를 새로고침한 뒤 실행하세요. 콘솔이 별도로 보여주는 undefined는 마지막 명령의 반환값일 수 있습니다.

아래에서는 B 객체를 먼저 만들고 A 객체의 next에 넣습니다. null은 “다음 항목이 없다”는 뜻으로 사용합니다. 우선 출력이 A, B로 이어지는지만 확인한 뒤 나머지 줄을 읽어 보세요.

const second = { value: "B", next: null };
const first = { value: "A", next: second };
console.log(first.value);
console.log(first.next.value);
console.log(first.next === second);
second.value = "바뀐 B";
console.log(first.next.value);

출력:

A
B
true
바뀐 B

줄	뜻과 필요한 이유
const second = { value: “B”, next: null };	B라는 값과 다음 항목 없음(null)을 가진 객체 하나를 만듭니다.
const first = { value: “A”, next: second };	A 객체를 만들고 next가 앞에서 만든 B 객체를 가리키게 합니다. B를 새로 복사하는 것이 아닙니다.
console.log(first.value);	A 객체 자신의 값을 읽습니다.
console.log(first.next.value);	A의 next를 한 번 따라간 뒤 그 객체의 값 B를 읽습니다.
console.log(first.next === second);	두 표현이 같은 B 객체를 가리켜 true입니다. 내용만 같은 별도 객체라는 뜻이 아닙니다.
second.value = “바뀐 B”;	기존 B 객체 안의 value를 바꿉니다.
console.log(first.next.value);	같은 객체를 읽으므로 바뀐 B가 나옵니다.

여기서 중요한 것은 참조라는 말입니다. first.next에는 B 객체를 찾아갈 수 있는 연결을 저장합니다. second도 first.next도 같은 객체로 갑니다. 따라서 second를 통해 값을 바꾸면 first.next로 읽을 때도 바뀐 값을 봅니다. 객체를 복제해 따로 보관한 것이 아닙니다.

const는 변수 second에 다른 객체를 다시 대입하지 못하게 합니다. 객체 안의 second.value까지 변경 금지로 만드는 것은 아닙니다. 이 차이를 알아야 다음 단계의 next 변경도 자연스럽게 읽을 수 있습니다.

3. A → B → C에서 B를 건너뛰어 봅니다

이제 세 노드를 만들겠습니다. 연결 리스트에서 중간 항목을 제외한다는 것은 남은 모든 값을 앞 칸으로 옮기는 일이 아닙니다. A의 다음을 B 대신 C로 바꾸면 A에서 출발하는 경로가 A → C가 됩니다.

시점	A의 next	B의 next	A에서 따라간 경로
바꾸기 전	B	C	A → B → C → null
A의 next를 B의 next로 변경	C	C	A → C → null

const nodeC = { value: "C", next: null };
const nodeB = { value: "B", next: nodeC };
const nodeA = { value: "A", next: nodeB };
console.log(nodeA.next.value);
nodeA.next = nodeB.next;
console.log(nodeA.next.value);
console.log(nodeB.value);

출력:

B
C
B

nodeA.next = nodeB.next에서 오른쪽 nodeB.next는 C 객체입니다. 따라서 이 줄은 A의 next를 C로 바꿉니다. nodeA.next = null이라면 B뿐 아니라 C로 가는 길도 끊어집니다. “어디를 없앨까”보다 “남은 앞뒤를 어떻게 다시 이을까”를 먼저 생각하세요.

마지막 출력이 여전히 B인 것도 중요합니다. 연결에서 건너뛰었다고 B 객체 자체가 즉시 삭제된 것은 아닙니다. 이 예제에는 nodeB라는 변수가 아직 B 객체를 가리키고 있어 읽을 수 있습니다. 바뀐 것은 A에서 시작해 따라가는 경로입니다.

4. 잠깐, 한 줄만 바꾼다면?

A → B → C → null에서 A만 남기려면 A의 next를 무엇으로 바꿔야 할까요? 반대로 A → C를 만들려면요?

답과 이유 확인하기

A만 남기려면 nodeA.next = null입니다. A → C를 만들려면 nodeA.next = nodeC 또는 nodeA.next = nodeB.next입니다. 다음 표시를 어디로 바꾸느냐에 따라 이어서 읽을 수 있는 항목이 달라집니다.

5. 첫 항목과 마지막 항목을 따로 기억합니다

지금까지는 nodeA, nodeB처럼 노드를 이미 알고 있었습니다. 항목이 많이 늘어나면 모든 변수 이름을 따로 만들 수 없습니다. 그래서 목록의 첫 노드를 head, 마지막 노드를 tail이라는 두 변수로 기억하겠습니다. head와 tail은 새 노드가 아니라 기존 노드를 가리키는 표시입니다.

목록	head가 가리키는 곳	tail이 가리키는 곳
비어 있음	null	null
A → null	A	A
A → B → null	A	B
A → B → C → null	A	C

한 노드만 있을 때는 첫 노드와 마지막 노드가 같으므로 head와 tail이 같은 객체를 가리킵니다. head는 앞에서 읽을 때 필요합니다. tail은 끝에 새 노드를 붙일 때 필요합니다. tail이 없다면 마지막 노드를 찾기 위해 매번 처음부터 next를 따라가야 합니다.

6. 뒤에 붙일 때는 연결부터, 마지막 표시를 그다음에

A 하나가 있을 때 B를 뒤에 붙여 보겠습니다. 해야 할 일은 두 가지입니다. 먼저 현재 마지막 A의 next를 B로 연결하고, 그다음 “이제 마지막은 B”라고 tail을 바꿉니다.

const start = { value: "A", next: null };
let tail = start;
const added = { value: "B", next: null };
tail.next = added;
tail = added;
console.log(start.next.value);
console.log(tail.value);

출력:

B
B

단계	목록의 연결	tail
처음	A → null	A
tail.next = added	A → B → null	아직 A
tail = added	A → B → null	B

tail = added를 먼저 실행하면 tail은 이미 B입니다. 그 뒤 tail.next = added를 실행하면 B가 자기 자신을 가리키고, A와 B는 연결되지 않습니다. 그래서 기존 마지막 노드를 가리키고 있을 때 next를 먼저 바꾸어야 합니다.

목록이 비었을 때는 연결할 기존 마지막 노드가 없습니다. 이 경우 새 노드를 head로 정하고 tail도 같은 새 노드로 정하면 됩니다. 아래 전체 코드의 if (tail === null)이 바로 이 경우를 나눕니다.

7. 앞에서 꺼낼 때는 값을 먼저 기억합니다

A → B에서 A를 꺼내면 새 첫 노드는 B입니다. B의 위치를 계산할 필요는 없습니다. 기존 첫 노드의 next가 이미 B를 가리킵니다.

const last = { value: "B", next: null };
let head = { value: "A", next: last };
const removed = head;
head = removed.next;
console.log(removed.value);
console.log(head.value);

출력:

A
B

const removed = head로 기존 A를 먼저 기억하고, head = removed.next로 시작점을 B로 옮깁니다. 그러면 A를 반환하면서도 목록은 B에서 계속 읽을 수 있습니다. head를 먼저 바꾼 뒤 head.value를 반환하면 A가 아니라 B를 잘못 돌려주게 됩니다.

A 하나만 있는 목록에서 앞의 A를 꺼냈습니다. head는 null이 되었습니다. tail은 A를 그대로 가리켜도 될까요?

답과 이유 확인하기

아닙니다. 이제 마지막 노드도 없으므로 tail도 null로 바꿔야 합니다. tail에 옛 A가 남으면 다음 추가를 “이미 노드가 있는 목록”으로 잘못 처리할 수 있습니다. 빈 목록에서는 head와 tail이 함께 null입니다.

8. 뒤 추가와 앞 제거만 있는 전체 코드

오늘은 append(뒤에 추가), removeFirst(앞에서 꺼내기) 두 동작만 묶습니다. 문자열과 숫자만 저장하며 null은 빈 목록의 반환값으로 예약합니다. 같은 값을 두 번 추가하면 서로 다른 노드 두 개가 됩니다. 이 입력 약속을 검사하는 코드는 생략했습니다.

createList()는 head와 tail을 기억하며 두 함수를 묶어 돌려줍니다. list.append(“A”)처럼 호출하면 내부 연결이 바뀝니다. 아래는 사용 예제까지 포함한 전체 코드이며, 앞선 코드 블록을 실행하지 않았어도 단독으로 실행됩니다.

function createList() {
  let head = null;
  let tail = null;

  function append(value) {
    const node = { value, next: null };
    if (tail === null) {
      head = node;
    } else {
      tail.next = node;
    }
    tail = node;
  }

  function removeFirst() {
    if (head === null) return null;
    const firstNode = head;
    head = firstNode.next;
    if (head === null) tail = null;
    return firstNode.value;
  }

  return { append, removeFirst };
}

const list = createList();
list.append("A");
list.append("B");
list.append("C");
console.log(list.removeFirst());
console.log(list.removeFirst());
console.log(list.removeFirst());
console.log(list.removeFirst());
list.append("D");
console.log(list.removeFirst());

출력:

A
B
C
null
D

append 안의 새 node는 value와 next:null만 있으면 됩니다. 목록이 비었으면 head를 새 노드로 정하고, 그렇지 않으면 기존 tail.next로 이어 줍니다. 어느 경우든 마지막은 새 노드이므로 if 뒤에서 tail = node를 실행합니다.

removeFirst는 head가 null이면 즉시 null을 반환합니다. 노드가 있으면 그 노드를 firstNode에 보관하고 head를 다음으로 옮깁니다. 새 head까지 null이면 마지막 노드를 꺼낸 것이므로 tail도 null로 바꿉니다. 마지막 줄은 보관해 둔 옛 첫 노드의 값을 반환합니다.

return { append, removeFirst }는 밖에서 사용할 두 함수를 묶어 주는 줄입니다. 이 글의 완성 버전에서는 밖에서 head나 tail을 직접 바꾸지 않고 이 두 함수를 사용합니다. 앞선 수동 예제에서 직접 바꾸던 연결을 함수가 같은 순서로 대신 바꾸는 것입니다.

9. 비었다가 다시 추가하는 순간까지 확인합니다

동작	남은 목록	head	tail	반환값
A, B, C 추가	A → B → C	A	C	없음
첫 번째 removeFirst	B → C	B	C	A
두 번째 removeFirst	C	C	C	B
세 번째 removeFirst	비어 있음	null	null	C
빈 상태에서 removeFirst	비어 있음	null	null	null
D 추가	D	D	D	없음
다시 removeFirst	비어 있음	null	null	D

처음부터 모든 삭제 방법을 외울 필요는 없습니다. 먼저 이 표의 빈 목록 → 한 노드 → 여러 노드 → 빈 목록을 설명할 수 있으면 됩니다. 특히 첫 노드가 마지막 노드이기도 한 순간이 head와 tail을 함께 바꾸는 이유입니다.

10. 재생 대기 목록 문제로 이어갑니다

재생 목록 앞곡 처리에서는 ADD를 append에, PLAY를 removeFirst에 대응시킬 수 있습니다. LIST는 항목을 꺼내지 않고 head부터 next를 따라가며 모든 곡을 읽는 추가 동작입니다. 우선 ADD와 PLAY만 손으로 처리한 뒤 LIST를 더해 보세요.

연결된 문제에는 입력 처리와 LIST까지 포함한 별도의 전체 정답이 있습니다. 그 정답의 빈 결과 표시는 {done:true}이고 이 글의 간단한 버전은 null입니다. 반환 형식을 그대로 섞지 말고 “비었는지 확인하고 첫 곡을 꺼낸다”는 같은 순서를 비교하세요.

더 알아보기: 중간 값 찾기와 삭제는 왜 따로 배울까요?

B를 이미 알고 있을 때 연결을 바꾸는 것은 짧았습니다. 하지만 이름 B만 주어지면 먼저 head부터 하나씩 찾아야 합니다. 중간 삭제에는 B 바로 앞 노드도 알아야 합니다. 그래서 find와 remove(value)는 앞 제거보다 단계가 더 많으며 이 글의 기본 구현에서는 다루지 않습니다.

뒤 추가와 앞 제거는 목록 전체를 훑지 않고 몇 개의 연결만 바꿉니다. 반대로 몇 번째 값을 바로 읽거나 전체 값을 출력하려면 next를 따라가야 합니다. 위치로 자주 읽는 작업에는 배열 글의 방식이 더 간단할 수 있습니다. 연결 리스트가 모든 작업에서 더 빠른 것은 아닙니다.

참고 연습

백준 1406 에디터는 커서 위치의 편집을 다루는 별도 문제입니다. 이 글의 두 메서드만으로 곧바로 해결되는 문제는 아니므로 재생 목록 연습 뒤에 살펴보세요. 외부 문제 지문과 예시는 옮기지 않았습니다.