오늘의 공부

연결리스트

Linked-List

연결리스트는 말 그대로 연결된 리스트이다. 물리적으로 흩어져 있는 자료들을 서로 연결해 하나로 묶는 방법인 것이다.

배열을 이용한 자료구조는 구현이 간단하지만 용량이 고정된다는 단점이 있다. 배열은 동적으로 크기를 늘리거나 줄일 수 없어서 처음 할당한 공간이 가득 차면 더 이상 데이터를 추가할 수 없기 때문이다.

그렇다면 연결리스트는? 데이터와 링크로 구성돼 있고 링크가 노드들을 연결하는 역할을 한다. 따라서 노드들의 연결만 바꿔주면 되니까 용량이 자동으로 변할 수 있는 것이다. 

그래서 배열에 비해 중간에 자료를 삽입하는 것이 용이하고 크기가 고정되지 않는다. 

배열에서 어떤 자료를 추가하고자 할 때는 그 위치 이후의 자료를 한 칸씩 뒤로 복사해 넣어주고 그 자리에 자료를 넣어줘야 한다.

하지만 연결 리스트에는 이럴 필요가 없다.

왜? 

◎ 삽입과 삭제 

위와 같이 노드들이 연결되어 있다고 할 때 (A->B->C->D->E) 데이터를 삽입하고자 한다. 

B와 C사이에 N을 삽입하려고 한다면? 

이렇게 B와 C를 연결해 주던 것을 없애고 B를 N과 N과 C를 연결한다. 그러면 A->B->N->C->D->E 순으로 연결되며 B와 C사이에 N이 위치하게 된다. 

삭제도 마찬가지이다. 

C를 없애고 싶다면 C로 연결되던 B와 D의 선을 지우고 B와 D를 연결시켜 주면 된다. 

◎ 연결리스트의 구조

연결리스트의 구조에는 크게 두 가지 노드와 헤드포인터가 있다.

○ 노드 (node)

위의 그림에서 A,B,C,D,E에 해당하는 것들이 노드이다. 연결리스트는 노드들의 집합이고 이들은 데이터를 저장하고 있으며 서로 연결되어 있다.

이 노드는 데이터를 담는 데이터 필드와 링크를 담는 링크 필드로 구성되어 있다.

데이터 필드에는 말 그대로 데이터가 들어간다. 담고 싶은 정보를 담는 곳이다. 정수가 될 수 있고 구조체가 될 수도 있다. 

링크 필드에는 다른 노드를 가리키는 정보가 들어있다. 위 사진에서는 화살표에 해당하며 다른 노드의 주소를 저장하는 포인터 변수가 존재한다. 이 포인터를 이용해서 현재 노드에 연결되어 있는 다음 노드가 어떤 노드인지 알 수 있는 것이다. 

○헤드 포인터(head pointer)

헤드 포인터는 연결 리스트의 첫 번째 노드의 주소를 저장하는 포인터이다. 

연결 리스트는 첫 번째 노드를 알면 그 뒤에 매달려 있는 모든 노드들에 순차적으로 접근할 수 있다.

그래서 헤드 포인터 주소를 반드시 알아야 한다. 

(마지막 노드 같은 경우에는 더 이상 연결할 노드가 없는데 링크 필드의 값을 NULL로 설정해서 이 노드가 마지막 노드임을 표현한다.)

◎ 연결리스트의 특징 

- 노드들은 메모리의 어느 곳에나 위치할 수 있다.

즉, 노드들의 주소가 연결 리스트 상의 순서와 동일하지 않다. 인접한 노드라고 해서 인접한 메모리에 있는 것이 아니다.

- 연속적인 기억공간이 없어도 데이터를 저장하는 것이 가능하고 미리 공간을 확보할 필요도 없다. 필요할 때마다 동적으로 노드를 생성해서 연결하기 때문이다.

- 링크 필드를 위한 추가 공간이 필요하다.

- 연산의 구현이나 사용 방법이 배열에 비해 복잡하다.

- 오류가 없더라도 동적 할당과 해제가 너무 빈번하게 일어나면 메모리 관리를 위한 처리시간이 길어져 프로그램이 느려질 수도 있다. 

◎ 연결리스트의 종류

연결리스트는 연결의 종류에 따라 세 가지로 나뉜다.

1. 단순 연결 리스트

하나의 방향으로만 연결되어 있으며, 맨 마지막 녿의 링크 필드는 NULL 값을 가진다.

2. 원형 연결 리스트

단순 연결 리스트와 같지만 맨 마지막 노드의 링크 값이 다시 첫 번째 노드를 가리킨다. 그래서 원형으로 연결 되었다고 표현하는 것이다.

3. 이중 연결 리스트

각 노드마다 링크 필드, 즉 포인터가 2개씩 존재한다. 따라서 각각의 노드는 선행 노드와 후속 노드를 모두 가리킬 수 있다. 

참고 자료;

두근두근 자료구조 (출판사; 생능 출판 / 저 ;최영국, 천인국, 공용해 )