연결 리스트(Linked List)

순차 자료구조의 문제점은 삽입연산이나 삭제연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간 소요의 낭비가 있다. 원소들의 이동 작업으로 인한 오버헤드는 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능상의 문제가 발생한다.
순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법이 필요한데 그것이 연결 리스트이다.

 

연결 자료구조(Linked Data Structure)는 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조이다.
각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식이다. 이 방법은 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 크기 변경이 유연하고 더 효율적으로 메모리를 사용한다. 

 

<연결 리스트>

리스트를 연결 자료구조로 표현한 구조이다. 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트로 나뉜다.

 

[노드]

연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조

데이터 필드(data field)는 원소의 값을 저장하고, 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성된다.
링크 필드(link field)는 다음 노드의 주소를 저장하고, 포인터 변수를 사용하여 주소값을

저장한다.

 

예)

1. 리스트 이름 (week) - 연결 리스트의 시작을 가리키는 포인터변수
2. 포인터변수(week)는 연결 리스트의 첫번째 노드를 가리키는 동시에 연결된 리스트 전체를 의미한다.
3. 연결 리스트의 마지막 노드의 링크필드 - 노드의 끝을 표시하기 위해서 null(널) 저장
4. 공백 연결 리스트 - 포인터변수(week)에 null을 저장 (널 포인터)
5. 각 노드의 필드에 저장한 값은 포인터의 점 연산자를 사용하여 액세스
− week.data : 포인터 week가 가리키는 노드의 데이터 필드 값 “월”

− week.link : 포인터 week가 가리키는 노드의 링크 필드에 저장된 주소값 “120”

<단순 연결 리스트>

노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트이다. 연결 리스트, 선형 연결 리스트(linear linked list), 단순 연결 선형 리스트(singly linked linear list)라고도 한다.

 

[자유 공간 리스트]

사용하기 전의 메모리나 사용이 끝난 메모리를 관리의 용이성을 위해 노드로 구성하여 연결한 리스트다.

[자유 공간 리스트의 노드 할당 과정]

자유공간 리스트 Free에서 노드를 할당할 때는 항상 첫 번째 노드 할당

① new ← Free;

리스트 Free의 첫 번째 노드의 주소(Free)를 포인터 new에 저장하여 포인터 new가 할당할 노드를 가리키게 한다.

② Free ← Free.link;

포인터 Free에 리스트의 두 번째 노드의 주소(Free.link)를 저장

③ 위의 자유공간 리스트 Free의 첫 번째 노드는 리스트에서 의미적으로 분리된 상태이므로 포인터 new를 반환해줌으로써 새 노드를 할당

 

[자유 공간 리스트의 노드 반환 과정]

① old.link ← Free;
자유 공간리스트 Free의 첫 번째 노드주소(Free)를 반환할 노드 포인터 old.link에 저장하여 포인터 old의 노드가 리스트 free의 첫 번째 노드를 가리키게 한다.

 

② Free ← old;
포인터 old의 값 즉, 반환할 노드의 주소(old)를 포인터 Free에 저장하여 리스트 Free의 첫 번째 노드로 지정

Copyrightⓒ2014 By 한빛아카데미(주)