리스트와 단순 연결 리스트

연결 리스트

1. 연결 리스트란?

 * 리스트의 목록을 순서대로 연결한 것

 

2. 연결 리스트의 기초

typedef struct 
{ 
    int Data; //노드 내부의 실제 데이터 또는 레코드
    node* Next; //Next가 가리키는 것은 노드 타입
} node; //구조체에 노드라는 새로운 타입명 부여

typedef node* Nptr; //Nptr 타입이 가리키는 것은 노드 타입

Nptr p, q; //Nptr 타입 변수 p, q를 선언

 - 노드 이어붙이기

p = (node *)malloc(sizeof(node));
p->Data = 33;
p->Next = (node *)malloc(sizeof(node)); 
p->Next->Data = 22; 
p->Next->Next = NULL;

3. 출력, 삽입, 삭제

 1) 출력

Temp = Head; 
while (Temp != NULL) 
{ 
    printf("%d ", Temp->Data); 
    Temp = Temp->Next; 
}

 

 2) 삽입

p = (node *)malloc(sizeof(node)); 
p->Data = 8;
p->Next = Temp->Next;
Temp->Next = p;

 

 3) 삭제

p = Temp->Next; 
Temp->Next = Temp->Next->Next; 
free p;

여러 가지 연결 리스트

1. 이중 연결 리스트

- 삽입과 삭제

 * 단순 연결 리스트의 삽입

 * 테일 포인터가 따로 있으면 유리

 * 삭제일 경우에는 테일 포인터가 뒤로 이동

 * 이중 연결이어야 테일 포인터를 뒤로 이동할 수 있음

2. 원형 연결과 원형 이중 연결

1) 원형 연결

 * 타임 셰어링 시스템의 타임 슬라이스(cf. 멀티 프로스세 환경에서 CPU가 TASK를 분배)

 * 사용자 교대

2) 원형 이중 연결

 * 접근성이 좋아지지만, 값이 비싸다.

 * 중간 사슬이 끊어지면 전체적으로 구조가 무너지기 쉽다.

 

3. 배열과 원형 리스트의 비교

- 공간

  ▪ 배열은 정적이므로 최대크기를 미리 예상해야 함

  ▪ 만들어 놓은 배열 공간이 실제로 쓰이지 않으면 낭비

  ▪ 연결 리스트는 실행 시 필요에 따라 새로운 노드 생성

  ▪ 연결 리스트는 포인터 변수공간을 요함

 

- 검색 시간

  ▪ 배열은 단번에 찾아감(묵시적 어드레싱: 인덱스 연산)

  ▪ 연결 리스트는 헤드부터 포인터를 따라감(현시적 어드레싱: 포인터 읽음)

 

- 삽입, 삭제 시간

  ▪ 배열의 삽입: 오른쪽 밀림(Shift Right)

  ▪ 배열의 삭제: 왼쪽 밀림(Shift Left)

  ▪ 연결 리스트: 인접 노드의 포인터만 변경

 

- 어떤 자료구조를 선택할 것인가?

  ▪ 검색 위주이면 배열이 유리

  ▪ 삽입 삭제 위주라면 연결 리스트가 유리

  ▪ 최대 데이터 수가 예측 불가라면 연결 리스트