Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

'양방향 연결 리스트(doubly linked list)' 또는 '이중 연결 리스트' 라고도 불리는 이 자료구조는 그 이름이 의미하듯이 노드가 양쪽 방향으로 연결된 구조의 리스트이다.

즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

ex) data1-> <-data2 -> <-data3

더미 노드 양방향 연걸리스트도 있고, 원형 연결 기반의 양방향 연결 리스트 등등도 있다.

밑에 나오는 예제는 기본적인 양방향 연결 리스트이다.

서로 봐라보는 것이라 복잡하게 느껴진다. 하지만 실제로 코드를 비교해 보면 상대적으로 더 복잡하지 않음을 알 수 있다. 

양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서는 어렵게 구현했던 것이 쉽게 구현되기도 한다. 때문에 오히려 단순하게 느껴지는 측면도 있다.

예제

이 예제에서는 배열의 단점을 분명히 보여주고 있다.

"배열은 메모리의 특성이 정적이어서(길이의 변경이 불가능해서) 메모리의 길이를 변경하는 것이 불가능하다."

위 예제를 실행한 후 0 이하의 값을 입력하지 않고 계속해서 자연수만 입력을 하면 할당된 배열의 길이를 넘어서는 문제가 발생한다. 

이렇듯 특성이 정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다. 그래서 등장한 것이 '동적인 메모리의 구성' 이다.

프로그램 실행 중에 필요할 때마다 메모리 공간을 마련하는 유일한 방법은 "malloc 또는 그와 유사한 성격의 함수를 호출하는 메모리의 동적 할당" 이다.

연결 리스트의 기본 원리

"필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다."

동적할당으로 노드를 구성하는 예제)

자료구조는 코드를 통해서 공부하는 과목이 아니다. 코드를 통한 학습 이전에, 그림으로 설명하고 그림으로 이해해야 하는 과목이다.

위의 linked.c의 방식은 적절치 않다. 대표적인 두 가지 이유는 다음과 같다.

1. 연결 리스트의 ADT를 정의하지 않았다.

2. 삽입, 삭제, 조회의 기능이 별도의 함수로 구분되어 있지 않다.

즉, 위의 예제는 연결 리스트와 과련된 코드를 모조리 main 함수에다 집어넣었기 때문에 필요할 때 가져다 쓸 수 있는 형태가 아니다.