[자료구조] 배열 vs Linked List (연결리스트)

❓ 연결리스트와 노드

코딩테스트를 푸는 도중, 배열처럼 생긴 구조에 배열 메서드를 사용하려다가 타입 에러가 나서 확인해 보니,

연결리스트라는 걸 사용해야 풀 수 있는 문제였다.

그렇다면 연결리스트가 뭘까?

 

연결리스트는 데이터가 차례차례 연결된 일종의 체인이라고 할 수 있다.

쉽게 설명하자면, 마치 기차처럼 각 칸(노드)이 다른 칸과 연결되어 있는 구조이다.

하지만 배열과는 달리, 이 연결된 칸들이 메모리상에 연속적으로 배치되지는 않는다.

 

📌 연결리스트의 구조

연결리스트는 노드들이 하나씩 연결되어 이어진 구조를 갖고 있다.

연결리스트의 구조

• head: 연결리스트의 첫 번째 노드(시작점)를 가리키는 포인터
• tail: 마지막 노드를 가리키는 포인터
• null: 마지막 노드는 더 이상 연결된 노드가 없기 때문에 마지막 노드의 next 는 null 로 설정

 

📌 Node 의 구조

그럼 Node는 뭘까?

연결리스트의 핵심 구성 요소인 노드는 하나의 데이터 덩어리로, 두 가지의 중요한 정보를 담고 있다.

노드의 구조

• 데이터(data): 각 노드가 담고 있는 실제 정보(문자열, 숫자, object ...)
• 다음 노드를 가리키는 주소(next): 현재 노드가 다음 노드와 연결될 수 있도록 다음 노드의 위치(주소)를 기억

한 마디로, 노드는 데이터를 담고 있을 뿐 아니라 다음 데이터가 어디 있는지 알려주는 역할을 한다.

 

---

❓ 배열 vs 연결리스트

배열과 연결리스트의 차이점

📌 배열

배열은 프로그램에서 자주 사용하는 자료구조로, 모든 요소가 연속된 메모리 공간에 저장된다.

즉, 배열의 원소들이 메모리상에서 하나의 덩어리로 나란히 붙어있는 상태라고 생각하면 된다. (그림처럼!)

이 덕분에 배열은 특정 위치에 있는 값에 빠르게 접근할 수 있다. ➡️ arr[3] 이라고 하면, 바로 3번째 값을 가져올 수 있다.

이렇게 배열은 랜덤 접근(random access)이 가능하다는 장점이 있다.

 

히지만 배열은 새로운 데이터를 중간에 삽입하거나 삭제할 때 불편할 수 있다.

배열의 크기가 고정돼 있을 수 있고, 중간에 데이터를 추가하거나 삭제하면 나머지 원소들의 위치를 재배열해야 하기 때문이다.

그래서 배열에서 중간에 데이터를 삽입하거나 삭제하는 작업은 비효율적일 수 있다.

 

📌 연결리스트

반면 연결리스트는 각 노드가 메모리의 아무 곳에나 흩어져 있다.

각 노드가 포인터(다음 노드를 가리키는)를 가지고 있어, 이 포인터를 통해 다음 노드로 이동할 수 있다.

그래서 연결리스트는 새로운 노드를 쉽게 추가하거나 삭제할 수 있는 장점이 있다.

노드 사이의 연결만 바꿔주면 되니까, 배열처럼 나머지 데이터를 이동시킬 필요가 없는 것이다.

 

하지만 연결리스트는 랜덤 접근이 불가능하다.

배열처럼 arr[3] 으로 바로 3번째 요소에 접근할 수 없다.

연결리스트는 첫 번째 노드부터 차례차례 순서대로 따라가야 하기 때문에, 원하는 노드를 찾는 데 시간이 더 걸린다.

예를 들어, 10번째 노드를 찾으려면 첫 번째 노드부터 시작해 10번째 노드까지 도달해야 한다.

이 때문에 연결리스트에서의 탐색은 선형시간이 걸린다.

 

비교 항목	배열 (Array)	연결리스트 (Linked List)
메모리 저장 방식	연속된 메모리 공간에 저장	불연속적인 메모리 공간에 저장
접근 속도	빠름 (인덱스를 사용해 즉시 접근 가능)	느림 (첫 노드부터 순차적으로 탐색해야 함)
랜덤 접근 (Random Access)	가능 (인덱스로 바로 접근 가능)	불가능 (항상 첫 노드부터 순차적으로 접근)
삽입/삭제 속도	느림 (중간에 삽입/삭제 시 나머지 요소들을 이동)	빠름 (포인터만 수정하면 됨
메모리 효율성	크기가 고정되거나 일정 크기 이상으로 할당될 수 있음	필요할 때마다 노드를 동적으로 할당
구조의 복잡성	간단함 (연속된 메모리 공간)	복잡함 (노드와 포인터로 연결)
사용 사례	빠른 탐색이 필요한 경우	빈번한 삽입/삭제가 필요한 경우

 

---

❓ 연결리스트 종류와 구현방법

📌 연결리스트 종류

1. Singly Linked List(단일 연결 리스트)

단일 연결 리스트

• 가장 기본적인 형태의 연결리스트
• 각 노드가 한 방향으로만 연결돼 있다. ➡️ 역방향으로는 이동 불가

 

2. Doubly Linked List(이중 연결 리스트)

이중 연결 리스트

• 양방향으로 연결된 리스트
• 앞뒤로 탐색하는 게 빠르다는 장점이 있다.
• 노드마다 2개의 포인터(next, prev)를 관리해 줘야 되기 때문에 데이터의 구조와 흐름이 복잡해질 수 있다.

 

3. Circular Linked List(원형 연결 리스트)

원형 연결 리스트

• 마지막 노드가 다시 첫 번째 노드와 연결된 구조
• 리스트가 끝나지 않고, 계속 순환할 수 있는 형태
• 무한 루프에 빠지지 않도록 주의!

 

📌 구현 방법

❗️ 노드 구현 방법

노드의 구조

class Node {
  constructor(data) {
    this.data = data; // 노드가 담고 있는 데이터
    this.next = null; // 다음 노드를 가리키는 포인터 (현재는 null 로 초기화)
  }
}

 

❗️ 연결리스트 구현 방법

연결리스트 구현 방법

let head = new Node("a"); // 1
head.next = new Node("b"); // 2
head.next.next = new Node("c"); // 3
head.next.next.next = new Node("d"); // 4

---

📖 정리

1. 연결리스트는 기차처럼 각각의 노드가 이어져 있는 데이터 구조이다.
2. 노드는 데이터(data)를 저장하고, 다음 노드를 가리키는 주소 정보(next)를 포함한다.
3. 배열은 메모리상 연속된 공간에 데이터가 저장되어 빠르게 접근 가능. 하지만 중간 삽입/삭제 느림
4. 연결리스트는 각 노드가 흩어진 메모리 공간에 있고, 포인터로 연결. 삽입/삭제가 빠르지만 접근 느림

---

💡 참고 자료

https://www.youtube.com/watch?v=K1PlysPgNZY

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

연결 리스트 - 위키백과, 우리 모두의 백과사전