List (연결리스트)

List ADT

객체: n개의 element 형으로 구성된 데이터의 순서있는 모임

연산:

• insert: 특정위치에 요소 추가
• inset_first : 맨 처음에 요소 추가
• insert_last : 맨 마지막에 요소 추가
• delete : 특정 요소 삭제
• clear
• get_entry : 특정요소의 index 반환
• get_length : 리스트 길이 반환
• is_empty 
• is_full
• print_list

연결리스트 (Linked list, 단순 연결 리스트)

연결리스트

하나의 노드는 데이터 필드와 link 필드로 이루어져 있음

link는 다음 노드를 가리키는 포인터 변수

가장 마지막 노드의 link는 NULL을 가리킴

Head pointer: 데이터가 들어있는 첫번째 노드를 가리키는 포인터, data 없음, link 값만 존재

(간혹 리스트 마지막 노드를 담은 포인터를 따로 사용하기도 함, 관리가 용이해짐)

 

각 노드들은 메모리 상의 임의의 위치에 존재하기 때문에 link는 각 노드에 접근할 수 있는 유일한 수단!

장점

• 삽입과 삭제가 용이하다
• 연속된 메모리 공간이 필요없다
• 크기 제한이 없다

단점

• 구현이 복잡하다
• 오류가 발생하기 쉽다

원형 연결리스트

마지막 노드의 link가 NULL이 아닌 데이터가 들어있는 첫번째 노드 주소를 담음

(헤드 포인터가 마지막 노드를 가리키도록 구성하면 리스트 처음이나 마지막에 insert 연산이 용이)

 

기본형

헤드 포인터가 마지막 노드를 가리키는 경우

이중 연결리스트

선행 노드를 찾기 어려운 단순 연결리스트의 문제점을 해결 (원형 구조이기도 함)

공간을 많이 차지하고, 코드가 복잡해짐

 

Node가 2개의 link를 사용한다.

 

Head node (≠head pointer)

-데이터를 갖지 않는다

-노드 삽입, 삭제를 간단하게 할 목적으로 생성 및 사용

-리스트의 공백 상태에서는 head node 만 존재한다. (link는 자기 자신을 가리킴)

 

 이중 연결리스트 기본형