연결 리스트란? 배열의 한계를 넘는 자료구조 입문 정리

🧶 연결 리스트: 도입 — 배열을 넘어서

배열을 쓰면서 한 번쯤 이런 생각 해봤을지도 모른다.
“값 하나만 더 넣을 수 있으면 좋을 텐데...”
그런데 배열은 한 번 크기를 정하면, 메모리 상에서 ‘연속된 공간’에 데이터를 넣기 때문에 중간에 크기를 키우기 힘들다.

이럴 때 훨씬 더 유연하게 데이터를 저장할 수 있는 방식이 있다.
바로 연결 리스트(Linked List) 라는 자료구조다.

이번 글에서는 연결 리스트의 개념을 처음부터 천천히 이해해보려고 한다.
무엇보다 중요한 건:

“왜 이런 구조가 필요한가?”
이걸 느끼는 것이다.

 

데이터 구조란 무엇인가

컴퓨터는 모든 데이터를 메모리에 저장한다.
그런데 이걸 단순히 쌓아두는 게 아니라, 어떤 식으로 정리하고 연결하느냐에 따라 효율이 달라진다.
이걸 데이터 구조(Data Structure) 라고 부른다.

데이터 구조는 말 그대로 "데이터를 어떤 방식으로 구조화하느냐"에 대한 것이다.
그중 연결 리스트는 대표적인 구조 중 하나다.

 

배열과 연결 리스트의 차이

배열은 메모리 상에서 값들이 “쭉 나란히” 저장되어 있다.
이 말은, 인덱스 0에 있는 값 옆에는 바로 인덱스 1의 값이 있다는 뜻이다.

하지만 꼭 그래야만 할까?
만약 각 값을 메모리 여기저기에 흩뿌려 두고,
각 값이 다음 값이 어디 있는지만 기억하고 있다면?

그게 바로 연결 리스트다.

 

연결 리스트란 무엇인가

연결 리스트는 이렇게 생긴 구조다:

[값1 | 다음주소] → [값2 | 다음주소] → [값3 | NULL]

• 각 칸을 node(노드)라고 부른다.
• 각 노드는 자신의 값(number)과 다음 노드를 가리키는 주소(*next)를 함께 가지고 있다.
• 마지막 노드는 더 이상 연결할 게 없기 때문에 NULL을 가리킨다.

코드로 연결 리스트 표현하기

연결 리스트의 핵심은 바로 노드(node) 를 정의하는 구조체다.

typedef struct node {
    int number;
    struct node *next;
} node;

여기서 중요한 포인트들이 몇 가지 있다:

1. number는 그냥 값이다

예: 1, 42, 999 같은 정수

2. *next는 다음 노드를 가리키는 포인터다

예를 들어 지금 노드가 값 1을 가지고 있다면,
*next는 값 2를 가진 노드의 주소를 가리킨다.

3. typedef struct node { ... } node; 는 무슨 뜻일까?

C에서는 구조체를 만들 때 원래는 이렇게 써야 한다:

struct node n1;

하지만 typedef를 쓰면 struct node 대신 그냥 node라고 써도 된다:

node n1;

여기서 typedef struct node 뒤에 node를 붙이는 이유는,
구조체 안에서 자기 자신을 참조하려면 미리 이름을 선언해줘야 하기 때문이다.

 

 

그럼 NULL은 뭘까? 그리고 \0이랑 같은 거야?

❌ 아니다! 둘은 완전히 다르다.

구분 NULL \0

자료형	포인터 (node *, int *, ...)	문자형 (char)
의미	아무것도 가리키지 않음 (주소 X)	문자열의 끝을 표시하는 문자
정수값으로는	0	0
용도	연결 리스트 끝, 포인터 초기화 등	문자열 종료 ("hello\0"처럼)

📌 즉,

• NULL은 연결 리스트에서 “다음 노드 없음”을 나타낼 때 사용.
• \0은 문자열의 끝을 나타내는 특수 문자.

같아 보이지만 용도와 문맥이 완전 다르다!

 

연결 리스트의 장점

배열은 크기가 고정돼 있다.
연결 리스트는 새로운 값을 추가할 때, 메모리 어딘가에 새로운 노드를 만들어서 기존 노드와 연결만 하면 된다.

• 중간 삽입/삭제에 유리
• 크기 제한이 없음
• 메모리 재배치가 필요 없음

단점도 있다:

• 임의 접근이 느림 (list[3] 이런 게 안 됨)
• 포인터 관리가 까다로움

---

연결 리스트와 배열, 언제 어떤 걸 써야 할까?

• 데이터 양이 자주 변한다면? → 연결 리스트
• 빠른 인덱스 접근이 필요하다면? → 배열