연결 리스트

연결 자료구조

1. 순차 자료구조의 문제점

- 문제점

 1) 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간 소요

* 원소의 개수가 많을수록 원소들이 이동 작업으로 인한 오버 헤드가 많음

 * 삽입, 삭제, 연산이 많이 발생하는 경우에 성능 상의 문제 발생

 

 2) 순차 자료구조는 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐

 

2. 연결 자료구조의 정의

- 연결 자료구조(Linked Data Structure)

  : 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조

 * 각 원소에 저장되어 있는 다음 원소의 주소(Pointer)에 의해 순서가 연결되는 방식

 -> 물리적인 순서를 맞추기 위한 오버 헤드가 발생하지 않음

 * 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현

 -> 크기 변결이 유연하고, 더 효율적으로 메모리를 사용

 

- 연결 리스트

 * 리스트를 연결 자료구조로 표현한 구조

 

- 연결 리스트의 노드

 * <원소, 주소>의 구조

3. 연결 자료구조의 이해

- 노드 연결 방법에 대한 이해(기차놀이)

 * 기차놀이 하는 아이들: 연결 리스트의 노드

 * 이름표: 노드의 링크 필드

 

- 선형 리스트와 연결 리스트의 비교

 * 선형 리스트 논리 구조

 * 연결 리스트의 논리 구조

▪ 리스트 이름 week: 연결 리스트의 시작을 가리키는 포인터 변수
- 포인터 변수 week는 연결 리스트의 첫 번째 노드를 가리키는 동시에 연결된 리스트 전체를 의미
▪ 연결 리스트의 마지막 노드의 링크 필드: 노드의 끝을 표시하기 위해서 null 저장
▪ 공백 연결 리스트: 포인터 변수 week에 null을 저장(널 포인터)

 * 구조체 정의

typedef struct Node{ 
	char data[4]; 
	struct Node* link; 
};

 

단순 연결 리스트

1. 단순 연결 리스트의 정의

- 단순 연결 리스트(Singly Linked List)

▪ 노드 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트

 

1. 단순 연결 리스트의 삽입

▪ 예제 1) 리스트 week2 = (월, 금, 일) 에서 원소 "월"과 "금" 사이에 새 원소 "수" 삽입하기

 1) 삽입할 새 노드를 만들 공백 노드를 메모리에서 가져와서 포인터 변수 enw가 가리키게 함

 2) new의 데이터 필드에 “수”를 저장함

 3) new의 앞 노드, 즉 “월” 노드의 링크 필드값을 new의 링크 필드에 저장함

 4) new의 값(new가 가리키고 있는 새 노드의 주소)을 “월” 노드의 링크 필드에 저장함

3. 단순 연결 리스트의 삭제

- 예제 2) 리스트 week2 = (월, 수, 금, 일) 에서 원소 "수" 삭제하기

 1) 삭제할 원소의 앞 노드(선행자)를 찾음

 2) 삭제할 원소 “수”의 링크 필드 값을 앞 노드의 링크 필드에 저장함

- 자유 공간 리스트(Free Space Lise)

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

- 자유 공간 리스트에서의 노드 할당 과정

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

 1) new ← Free;

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

 2) Free ← Free.link;

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

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