data structure(자료 구조) - Linked list(연결 리스트)::FBTT

앞서 리스트와 배열의 차이에 대해서 언급한 적이 있습니다.

https://readytoearndon.tistory.com/21

data structure(자료 구조) - List(리스트)와 Array(배열)::FBTT

이때 배열(array)을 이용해 구현한 리스트를 순차 리스트, linked node(pointer)를 이용해 구현한 리스트를 연결 리스트라고 했었습니다.

 

지난번에 배열에 대해서 공부했으니 이번에는 연결 리스트에 대해서 알아보겠습니다.

 

연결 리스트와 배열을 비교하며 공부하면 좋을 것 같습니다.

https://readytoearndon.tistory.com/25

data structure(자료 구조) - Array(배열)와 search(탐색)연산::FBTT

위 글에는 배열에 대해 간략하게 설명되어 있습니다.

 

배열은 연속된 저장 공간에 그룹으로 저장되는데 반해 연결 리스트는 메모리의 임의의 위치에 data가 저장됩니다.

 

그러면 '연결 리스트는 자료를 관리하기가 배열에 비해 어려워지는 것이 아닌가요?'라고 생각할 수 있습니다.

 

그래서 연결 리스트에는 다음 자료에 접근할 수 있는 link가 존재합니다.

연결 리스트라고 불리는 이유이죠

 

서로 다른 위치에 존재하는 자료들이 link로 연결되어 있어 접근을 가능하게 합니다.

 

다음 자료로 접근하기 위해 다음 data가 존재하는 주소를 자기 자신의 data와 함께 저장하고 있습니다.

 

그래서 연결 리스트에 저장하는 자료를 node라고 부릅니다. 이 node에는 data와 다음 data의 주소를 저장하는 link를 함께 저장하고 있습니다.

 

단일 연결 리스트

 

연결 리스트에도 여러 종류가 있습니다.

1. 단일 연결 리스트
2. 이중 연결 리스트
3. 원형 연결 리스트

연결이 어떻게 되어있느냐에 따라 이름이 달라집니다

단일 연결 리스트는 한 방향으로 연결되고 이중 연결 리스트는 양방향으로 연결되어 있습니다.

배열과 연결 리스트의 차이

	배열	연결 리스트
메모리 공간	연속된 공간	임의의 공간
공간 할당	정적 할당/동적 할당	동적 할당
접근 경로	첫 번째 원소의 주소	첫 번째 원소의 주소
접근 방법	index	pointer
접근 방식	random access	sequential access

 

배열은 random access이고 연결 리스트는 sequential access라고 했는데 그 의미를 알아보겠습니다.

 

random access

원소가 어디에 있든지 접근하는데 걸리는 시간이 모두 동일함을 뜻합니다.

 

예를 들어 길이가 n인 arr라는 배열이 있는데 arr[0]이든 arr[n - 1]이든 접근하는데 걸리는 시간은 같습니다.

 

sequential access

원소의 위치와 접근 하는데 걸리는 시간이 연관이 있음을 의미합니다.

 

연결 리스트에 대해서 간단히 말씀드렸지만 다음 원소가 저장되어 있는 위치는 그 전 순서의 자료만 가지고 있기 때문에 n번 째 순서의 자료에 접근하기 위해서는 1번 째 자료부터 순서대로 접근해야 하기 때문에 원소의 위치와 접근 시간이 연관성을 가지게 됩니다.

 

다음에는 단일 연결 리스트, 이중 연결 리스트를 간단하게 구현해보도록 하겠습니다.