[Data Structure] Linked List

Linked List

이번 시간에는 Linked List(링크드 리스트)에 대해 알아보도록 할까요? 링크드 리스트란, 조금 발전된 형태의 배열 정도로 볼 수 있을 것 같아요!

흔히 배열을 생각한다면(모르셔도 괜찮아요! 밑에서 간략하게 설명해 드릴게요!) int나 char 등의 기본 자료형을 연속된 공간에 배치하는 방식을 생각할 수 있을 것 같아요. 이렇게 하면 공간 효율성은 좋을 수는 있지만, 중간에 있는 원소를 삭제하기도 어렵고, 고정된 크기를 벗어나기도 어렵다는 단점이 존재하죠. 뿐만 아니라, 연속된 공간이 존재하지 않으면 배열을 만들기도 어렵다는 단점 역시 존재합니다.

링크드 리스트는 이러한 단점들을 보완하기 위해 만들어진 Data Structure입니다.

---

배열이란?

우선, 배열에 대해 잘 모르는 분들이 계실 수 있어 설명을 드릴게요! 배열을 잘 알고 있다면 건너뛰어도 괜찮습니다.

예를 들어, 주사위를 굴려 나온 숫자를 저장하였다가 출력하는 프로그램이 있다고 가정해 봅시다. 배열을 알지 못하는 상태에서는 이를 어떻게 표현할까요?

// 주사위 변수 생성
int die1;
int die2;
int die3;
...
int die10;

// 주사위 값 입력
std::cin >> die1;
std::cin >> die2;
std::cin >> die3;
...
std::cin >> die10;

// 주사위 값 출력
std::cout << "your die1 num: " << die1 << std::endl;
...
std::cout << "your die10 num: " << die10 << std::endl;

총 10개의 주사위 값을 입력하려면 이런식으로 모든 내용을 10번 반복해야 합니다. 엄청나게 불편하죠?

배열을 사용하면 같은 이름의 변수에 여러 가지 값을 담을 수 있습니다. 자세한 건 코드를 같이 보고 얘기할까요?

// 주사위 세팅
int dice[10];

// 주사위 값 입력
for(int i = 0 ; i < 10 ; i++)
	std::cin >> dice[i];
    
// 주사위 값 출력
for(int i = 0 ; i < 10 ; i++)
	std::cout << "your die" << i+1 << " num: " << dice[i] << std::endl;

훨씬 짧고 간결하죠? 이런식으로 표현하는 것이 바로 배열입니다.

배열은 연속된 공간에 비슷한 의미를 가진 값들을 늘어놓는 방식이죠.

 

하지만 위에서 언급한 것과 같이 배열의 경우 다음과 같은 문제가 생길 수도 있습니다.

1. 고정된 크기로 인한 저장 장소 부족 및 메모리 낭비

2. 연속된 공간이 필요

3. 중간 원소의 추가/삭제가 비효율적

---

Linked List란?

앞서 언급된 배열의 단점을 해결하기 위해 나온 방식이 바로 Linked List(링크드 리스트) 입니다.

링크드 리스트는 한국 말로 연결 리스트라고도 하며, 이름답게 각각의 원소를 연결해 놓은 리스트 입니다.

자세히 알아볼까요?

간단한 Linked List

이렇게 보면 배열과 뭐가 다르지 싶을 수도 있죠? 하지만, 저 화살표는 단순히 다음 List를 의미하는게 아니라, 다음 List의 주소를 가지고 있다는 뜻입니다. 다시 말해서, 각각의 원소들이 굳이 연속적으로 있을 필요는 없게 된다는 뜻 입니다.

---

그럼 무슨 장점이 있나요?

이렇게 만들면 무슨 장점이 있을까요? 굳이 더 불편한 길을 선택하는것 처럼 보일 수도 있어요. 하지만 앞서 말했듯 Linked List는 배열의 단점들을 해결하기 위해 나왔습니다. 그럼 그 단점들을 모두 해결하였을까요?

 

정답은 그렇다 입니다. Linked List는 우선 연속된 공간이 필요하지 않습니다. 다음 List의 주소값만 가지고 있으면 되기 때문에 굳이 고정이지 않아도 다음 원소를 찾아갈 수 있는 것이죠.

이를 통해 파생되는 다른 장점 또한 존재합니다. 바로 크기를 고정할 필요가 없다는 것 입니다. 원래 배열은 시작과 끝의 위치를 정해줍니다. 그래서 배열 안에 있는 칸을 다 사용하지 않으면 메모리가 낭비되는 경우도 발생하죠. 뿐만 아니라 배열 크기를 초과하여 값을 넣을 수도 없습니다. 하지만, Linked List의 경우, 그냥 뒤에 다음 원소의 위치를 나타내는 포인터 값만 넣어주면 되니 용량 문제에서 훨씬 자유로울 수 있습니다.

마지막으로, Linked List는 중간에 있는 원소를 삭제하기 쉽다는 장점도 가지고 있습니다. 이는 그림을 통해 확인해 볼까요?

Linked List에서의 중간 원소 삭제 과정

다음과 같은 과정을 거치면 쉽게 원소를 삭제할 수 있습니다.

1. 링크드 리스트를 하나 준비합니다.

2. 내용1의 next를 내용3으로 연결해 줍니다.

3. 내용2를 삭제합니다.

 

비슷한 방법으로 Linked List의 중간에 원소를 추가할 수도 있습니다.

Linked List에서의 중간 원소 추가

1. Linked List를 준비한다.

2. 내용3을 만들고 next를 내용2에 연결한다.

3. 내용1의 next를 내용3으로 변경한다.

 

간단하죠? 배열과 달리 이런 점이 있기 때문에 Linked List을 활용한다고 보시면 될 것 같습니다.

 

---

Linked List 역시 다른 DS와 마찬가지로 단점이 없는 구조가 아닙니다. 다만, 중간에 원소를 추가할 수 있다는 강력한 장점이 있기 때문에, 많은 경우, 배열을 대체하여 사용하기 좋습니다. 배열과 Linked List는 사용처에 따라 알맞게 선택하여 사용하면 더 효율 좋은 코드를 만들 수 있으니 알맞게 사용하시길 바랍니다~