<자료구조 알고리즘> 연결 리스트

연결리스트란?

배열에서 각 요소간의 연결이라는 개념이 추가된 자료구조이다. 연결리스트에는 여려개의 요소들이 들어있고 이 요소들은 특정한 방법을 통해 다음 요소와 서로 연결되어 있다. 이 연결을 타고 우리는 각 요소에 접근 할 수 있다. 이야기만 들으면 너무 추상적이니 아래 그림을 같이 보자.

 

 

위의 그림에서 네모는 연결리스트의 각 요소를 나타내며 다음 요소를 가르키고 있는 화살표가 요소 사이의 연결을 나타낸다. 

1. 연결 방식

연결리스트의 각 요소는 두가지로 구성되어 있다. 하나는 저장하려는 값이고, 다른 하나는 다음 요소의 주소값이다. 오른쪽 그림의 초록색 부분에 다음 요소의 주소를 저장해 위의 그림에서 화살표가 요소를 연결하는 것과 같은 역할을 한다. 

 

2. 접근 방식

해리포터를 읽어 보았다면 플루 가루라는 것을 알 것이다. 벽난로에서 초록색 플루 가루를 던지며 가고자 하는 곳을 이야기하면 다른 집의 벽난로로 순간이동을 할 수 있게 해준다. (해리포터를 모른다면 그냥 원하는 집으로 순간이동 할 수 있는 장치라고 생각하자) 갑자기 이 이야기를 왜 하는가 하면 이제 부터 각 연결리스트의 요소를 집이라고 생각하려 하기 때문이다. 다음 그림과 같은 마을이 있고 아래 그림에서의 노란색으로 표시된 몇개의 집에 중요한 물건이 보관되어 있다고 하자.

 

1. 우리는 물건이 있는 첫 번째 집을 제외하고는 집들이 어디인지 알지 못한다.

2. 각 집에는 벽난로(순간이동 장치)가 있다.

3. 물건이 있는 집에는 다음집의 주소가 적혀 있다.

 

 

이러한 곳에서 우리는 3번집에 있는 물건을 가지고 와 볼 것이다. 

 

 

지금 현재 우리는 1번집 밖에 알지 못하므로 1번집으로 들어간다. 

 

 

1번 집에 들어갔더니 2번집의 위치가 적혀 있다. 이를 이용해서 벽난로를 통해 2번 집으로 이동한다.

 

 

2번 집에 있는 3번집 주소를 이용하여 3번집으로 이동하여 우리가 원하는 물건을 얻을 수 있다.

 

 

실제 컴퓨터에서 마을은 메모리이며 집은 연결리스트의 각 요소이고 물건은 저장하고자 하는 데이터라고 할 수 있다.

위 예시에서 알 수 있듯이 연결리스트에서 중간 요소에 저장되어 있는 데이터를 읽기 위해서는 첫번째 요소부터 탐색해 나가야한다. 

 

3. 삽입과 삭제

배열은 데이터가 랜덤인 위치에 저장되는 것이 아니라 한줄로 연속해서 저장된다. 따라서 첫번째 요소의 위치만 알면 바로 n번째 요소의 위치를 알 수 있기 때문에 가운데 원소를 처음부터 모두 탐색하여 접근할 필요가 없다.

 

 

 

그렇다면 연결 리스트를 사용하는 이유가 무엇일까? 

요소의 추가와 삭제가 쉽다는 장점이 있기 때문이다. 배열에서 원소를 추가하려면 옆집에 추가해야 하는데 만약 그곳에 이미 다른 데이터가 저장되어 있다면? 기존의 데이터를 모두 복사해 빈집이 충분히 있는 다른 곳으로 옮겨 주어야 한다. 또한 중간에 있는 값을 제거하게 되면? 비어버린 집을 채워주기 위해 모든 데이터를 옮겨주어야 한다. 하지만 연결리스트라면 새로운 집을 하나 장만하여 다음 집 주소를 적어주고 이전 집에는 새로 장만한 집 주소를 적어주기만 하면 된다. 배열에 비해 훨씬 빠르게 수행 가능한 원소 삽입과 삭제에 대해 더 자세히 알아보자

 

원소 삽입

워소 A 뒤에 B가 연결되어 있는 아래 사진과 같은 연결리스트에서 A원소 뒤에 새로운 원소 N을 추가하는 방법을 알아보자.

 

 

먼저 원소 A에 저장된 B의 위치를 원소 N에 복사한다. 이렇게 되면 아래와 같이 A와 N이 모두 B를 가르키고 있는 상태가 된다.

 

다음 A에 원소 N의 위치를 저장해 주기만 하면 원소 삽입이 완료된다.

 

 

※여기서 주의할 점은 순서이다. 만약 A에 원소 N의 위치를 먼저 저장하게 된다면 B의 위치를 알 수 있는 방법이 없어지기 때문에 원소N과 원소B를 연결할 수 없다.

 

원소 삭제

원소의 삭제는 삽입의 과정을 정확히 반대로 수행해 주면 된다. A다음 N 다음 B로 이루어진 아래 그림과 같은 연결리스트에서 원소 N을 삭제 해 보도록 하자.

 

 

먼저 원소 N에 저장된 B의 주소를 원소 A에 복사한다. 이렇게 되면 아래와 같이 A와 N이 모두 B를 가르키고 있는 상태가 된다.

 

 

그런 다음 원소 N을 메모리에서 지워버리게 된다면 삭제가 완료된다.

 

 

※여기서도 당연히 순서가 중요하다. 만약 원소 N을 먼저 지워버리게 된다면 B의 위치를 알 수 있는 방법이 없어지기

때문에 원소A과 원소B를 연결할 수 없다.

 

 

 

 

 

이렇게 연결리스트라는 자료구조의 구조와 탐색방법 원소의 삽입 삭제 방법에 대해서 알아보았다. 다음 글에서는 이를 구현해 보도록 하겠다.