[자료구조] 연결 리스트

연결 리스트(Linked List)는 배열과 함께 가장 기본적인 자료구조입니다.
배열이 연속된 메모리 공간에 데이터를 저장한다면,
연결 리스트는 노드(Node)의 연결로 데이터를 저장하는 구조입니다.
배열과 달리 메모리가 연속적이지 않아도 되고, 중간에 데이터를 삽입하거나 삭제하기 쉬운 장점이 있습니다.

 

1. 연결 리스트란 무엇인가?

연결 리스트는 여러 개의 노드(Node) 가 서로 연결된 형태의 자료구조입니다.

각 노드는 다음 두 가지 정보로 구성됩니다:

• 데이터(Data) – 저장하려는 실제 값
• 다음 노드의 주소(Next) – 메모리 상의 위치 정보를 저장

이 노드들이 차례대로 이어지며,
가장 첫 번째 노드는 헤드(Head),
가장 마지막 노드는 꼬리(Tail) 이라 부릅니다.

 

2. 배열과 다른 점: 메모리 연속성이 필요 없다

배열은 모든 요소가 연속된 메모리에 저장되지만,
연결 리스트는 노드가 메모리 상의 아무 위치에 있어도 상관없다는 큰 특징이 있습니다.

 

따라서:

• 불연속적인 데이터 저장에 유리
• 데이터를 삽입하거나 삭제할 때 공간을 재배치할 필요가 없다

예를 들어 아래처럼 노드가 메모리 여기저기 흩어져 있어도
포인터(다음 노드 정보)만 연결하면 Linked List가 됩니다.

 

 

3. 접근 속도: 배열보다 느림 (O(n))

배열은 인덱스로 바로 접근할 수 있어 O(1)이지만,
연결 리스트는 순차적으로 앞에서부터 탐색해야 합니다.

즉:

• 1번째 노드를 찾기 → 헤드에서 한 번 이동
• 10번째 노드를 찾기 → 노드를 10번 이동
• N번째 노드 → O(n)

따라서 연결 리스트는 임의 접근(Random Access) 이 불가능합니다.

 

 

4. 삽입과 삭제에서 강력한 이유: 재정렬이 필요 없다

배열에서는 중간에 데이터를 넣거나 삭제하면
뒤에 있는 요소들을 모두 밀거나 당겨야 해서 O(n) 이 소요됩니다.

 

하지만 연결 리스트는?

• 삽입: 연결 관계만 바꾸면 됨
• 삭제: 특정 노드만 빼고 앞뒤 노드를 다시 연결하면 끝

즉:

삽입/삭제는 위치만 알고 있으면 O(1)

단, 삭제할 노드를 찾기 위해 탐색이 필요하다면 그 부분은 O(n)입니다.

 

 

 

5. 배열과 연결 리스트 - 핵심 비교 정리

항목	배열	연결 리스트
메모리 구조	연속적	불연속적
접근 속도	O(1) – 인덱스 접근	O(n) – 순차 탐색
삽입/삭제	느림(O(n))	빠름(O(1)) — 위치만 알면
장점	빠른 접근	유연한 구조, 삽입·삭제 유리
단점	크기 고정, 삽입·삭제 비효율	탐색 속도 느림

 

 

 

정리하면

 

연결 리스트는 데이터가 불연속적으로 존재해도 연결(Link)로 관리할 수 있는 유연한 자료구조입니다.
배열처럼 인덱스로 바로 접근할 수는 없지만,
삽입과 삭제가 매우 효율적이라는 큰 장점을 가집니다.

 

연결 리스트를 이해하면
스택(Stack), 큐(Queue), 그래프(Graph) 등 다양한 자료구조를
쉽게 이해하는 데 큰 도움이 됩니다.