배열과 연결 리스트

배열(array)은 같은 크기의 칸을 메모리에 연속으로 붙여 둔 자료구조(data structure)이고, 연결 리스트(linked list)는 원소마다 다음 원소의 주소를 들고 줄줄이 이어진 자료구조다. 배열은 번호로 바로 칸을 찾지만 중간에 끼워 넣기가 비싸고, 연결 리스트는 끼워 넣기가 싸지만 번호로 찾으려면 처음부터 따라가야 한다. 이 문서는 두 구조가 메모리에 놓이는 모양과, 그 모양 때문에 생기는 접근·삽입 비용의 맞교환을 다룬다.

배열: 연속 메모리와 O(1) 접근

배열은 칸들이 메모리에 빈틈없이 이어져 있다. 그래서 i번째 칸의 주소는 "시작 주소 + i × 칸 크기"라는 곱셈과 덧셈 한 번으로 나온다. 원소가 백 개든 백만 개든 계산 횟수가 같다. 그래서 칸 번호(인덱스, index)로 원소를 읽는 인덱스 접근은 O(1)이다. 이것은 원소 수 n이 늘 때 비용이 늘어나는 정도를 적는 빅오 표기법(Big-O notation)으로, O(1)은 n과 상관없이 일정하고 O(n)은 n에 비례해 늘어난다는 뜻이다.

대신 칸이 이어져 있어야 한다는 조건이 삽입과 삭제를 비싸게 만든다. 중간에 원소를 하나 끼우려면 그 뒤의 원소를 전부 한 칸씩 밀어야 하고, 지우면 전부 한 칸씩 당겨야 한다. 최악(맨 앞)에는 n개를 옮기므로 O(n)이다. 또 처음 잡은 크기가 고정이라 칸이 모자라면 더 큰 배열을 새로 잡아야 한다.

연결 리스트: 노드와 포인터

연결 리스트는 원소 하나를 노드(node)라는 단위에 담는다. 노드는 값과 다음 노드의 메모리 주소, 즉 포인터(pointer)를 함께 가진다. 노드끼리 포인터로 이어져 있으므로 메모리에 흩어져 있어도 된다.

다이어그램 로딩…

이 구조에서 k번째 원소를 읽으려면 첫 노드(head)부터 포인터를 k번 따라가야 하므로 O(n)이다. 반면 끼울 위치의 앞 노드를 이미 알고 있다면, 새 노드를 만들어 포인터 두 개만 바꾸면 된다. 다른 원소를 옮기지 않으므로 O(1)이다. 아래는 10 뒤에 15를 끼우는 모습이다. 새 노드가 20을 가리키게 하고, 10이 새 노드를 가리키게 바꾸면 끝난다.

다이어그램 로딩…

여기서 "위치를 이미 알면"이라는 조건이 중요하다. 위치를 찾는 데는 여전히 O(n)이 든다.

연결 방식에 따라 세 가지로 나뉜다.

• 단일 연결 리스트(singly linked list): 노드가 다음 노드만 가리킨다. 가장 가볍지만 뒤로 갈 수 없다. 노드를 지우려면 앞 노드의 "다음" 포인터를 지울 노드의 다음 노드로 바꿔야 하므로, 그 앞 노드를 따로 알아야 한다.
• 이중 연결 리스트(doubly linked list): 노드가 이전 노드와 다음 노드를 모두 가리킨다. 양방향으로 움직일 수 있고, 노드 하나만 주어져도 앞뒤를 이어 붙여 O(1)에 지울 수 있다. 대신 노드마다 포인터가 하나 더 든다.
• 원형 연결 리스트(circular linked list): 마지막 노드가 끝을 뜻하는 빈 값(null) 대신 첫 노드를 가리킨다. 끝에서 멈추지 않고 처음으로 돌아오므로, 여러 대상에게 순서대로 돌아가며 차례를 주는 라운드 로빈(round robin) 같은 곳에 쓴다.

이어지는 내용은 배열과 연결 리스트 2에서 다룬다.

면접 포인트

• "배열과 연결 리스트의 차이는?" → 연속 메모리·인덱스 O(1)·중간 삽입 O(n) vs 흩어진 노드·접근 O(n)·위치를 알면 삽입 O(1).
• "연결 리스트 삽입이 O(1)이라면서요?" → 위치를 이미 알 때만. 찾는 데 O(n).
• 단일 vs 이중: 이중은 노드 하나만으로 O(1) 삭제·역방향 이동, 대신 포인터 하나 더.