[자료구조 4장] - 연결리스트(2)

연결리스트(2)

단순 연결리스트

 

구조와 연결방법

저장하려는 연결리스트 구조의 노드들은 첫 노드부터 꼬리에 꼬리를 물고 한 방향으로 연결되어 있으며 마지막 노드의 포인터는 NULL 값을 가진다.

ex) 문자열의 집합 {"bake", "cake", "sake", "take"}을 알파벳 순서로 연결리스트에 저장하는 경우

연결리스트를 표현하는 일반적인 방법

헤드 노드 : 첫 번째 노드의 포인터

헤드 노드의 포인터를 잃으면 리스트 안의 전체 데이터에 접근할 수 없게 된다.

 

화살표는 다음 자료의 기억 장소 번지이며, 마지막 노드의 다음 데이터는 없으므로 NULL값을 가지게 된다. 이렇게 단순 연결리스트는 헤드 노드로부터 NULL 값을 가지는 노드까지 한 방향으로 연결되어 있다.

 

연결리스트를 사용하여 프로그램을 작성할 때, 리스트의 끝을 검사하는 경우를 제외하고는 대부분의 경우 특정 주소값을 검색하지 않는다.

 

순차리스트보다 연결리스트에서 임의의 삽입 및 삭제 연산이 더 편리한 이유

위 그림에서 cake와 sake 사이에 fake 삽입하기 위한 절차

1. 현재 사용하고 있지 않은 노드 하나를 가져온다. malloc 함수에 의하여 할당받으면 노드의 첫 주소를 돌려주는데 이를 npointer에 저장하였다고 하자.

2. 이 노드의 데이터 필드에 fake를 저장한다.

3. npointer의 링크 필드를, 현재 cake를 가진 노드의 링크 필드 내의 주소를 가리키도록 한다.

4. cake를 가진 노드의 링크 필드가 npointer를 가리키도록 한다.

=> fake를 삽입할 때 리스트에 있는 어떤 원소도 이동되지 않았다. 즉, 데이터를 이동시킬 필요가 없는 대신에 링크 필드를 위한 저장 공간이 추가로 필요하다. 마찬가지로 fake를 삭제할 때에도 어떤 데이터 이동도 필요 없다.

 

연결리스트를 만들기 위해서는 다음과 같은 기능이 필요

1. 노드의 구조, 즉 노드의 필드들을 정의하는 방법 : 이를 위해 설명하였던 자기참조구조체를 사용

2. 필요 시 노드를 생성하는 방법 : malloc 함수가 이 연산을 처리

3. 더 이상 필요하지 않은 노드의 삭제 방법 : free 함수가 이 연산을 처리

 

이와 같이 연결리스트에 각 데이터항목(노드)를 삽입하거나 삭제할 때 몇 번의 대입문으로 가능하기 때문에 시간복잡도는 O(1)으로 상수시간에 가능하다. 배열에서의 데이터의 삽입과 삭제는 다른 데이터 항목의 이동이 필요하기 때문에 데이터 항목의 수가 n인 경우 O(n)임을 확인한 것과 비교하여 효율적인 것을 알 수 있다.