2021.2.5 TIL : [자료구조] 연결리스트

연결 리스트는 말 그대로 앞, 뒤의 순서가 있는 리스트를 말한다. 

이는 배열과도 비슷한데, 배열 기반 리스트는 배열로 만들어서 그 순서를 알기 쉬운 반면(ex. arr[0], arr[1]), 연결 리스트는 1 ---> 2 이런 식으로 진행되기 때문에 다른 점이 있다.

 

배열 같은 경우는 기초 C 언어 강의(나의 경우는 CS50)에서 다루고 있기 때문에 별도로 주의깊게 살피지는 않았다.

다만 배열 기반 리스트는 다음과 같은 특징이 있었다.

1) 배열로 만들어 특정 위치에 뭐가 있는지 알 수 있다.

2) 데이터가 들어갈 공간에 맞게 미리 메모리를 할당해야 한다. (배열의 길이를 미리 알아야 함)

3) 원하는 위치로 삽입이 번거롭다. (하나의 데이터를 삽입할 시, arr[i+1] = arr[i] / 하나의 데이터를 삭제 시, arr[i] = arr[i+1]의 과정을 반복해야 함)

 

연결리스트는 반면에 포인터와 연관이 있다. 즉, 데이터 값과 포인터를 함께 하나의 자료형(구조체)으로 정의하여 사용할 수 있다. 오늘 배운 건 한 방향으로만 진행되는 연결 리스트로, 한 노드에 포인터가 한 개만 존재하는 것이다. 즉, 노드 안에 있는 포인터가 다음 노드를 가리키는 동적 할당의 방식을 이용했다. 이는 노드를 추가하고자 하는 위치 바로 앞에 있는 포인터의 방향만 바꿔주면 리스트의 중간 지점에서도 추가하거나 삭제하기가 쉽다. 또한 필요할 때마다 메모리를 할당 받기 때문에 효율적이다. 

 

여기서 주의할 점은 일반적으로 연결 리스트의 시작 노드는 헤드라고 하여 따로 관리 하는데, 별도의 데이터 값은 가지고 있지 않다. 또한, 가장 마지막 노드의 포인터는 NULL을 가리켜야 한다. (이를 통해 리스트의 끝을 파악할 수 있다. 마치 문자열의 마지막에 \0의 널 종단 문자를 넣는 것과 같음)

 

연결 리스트는 다음과 같은 특징을 갖는다.

1) 삽입과 삭제는 포인터만 바꾸면 가능하기 때문에 배열에 비해서 쉽다.

2) 배열과 다르게 특정 인덱스로 바로 이동하는 것은 불가하고, 처음부터 차례대로 검색해야 한다.

3) 추가적인 포인터 변수가 데이터의 수만큼 사용되니 메모리 낭비가 발생한다. 

 

오늘 배운 내용은 이 정도이다.

연결 리스트와 배열이 서로 다른 장단점을 갖고 있기 때문에, 어떤 자료에서는 어떤 리스트가 더 효율적인지를 생각해 볼 필요가 있을 것 같다.