자료구조: CHAP 4 리스트 (3) 2017. 5. 2 순천향대학교 컴퓨터공학과 하 상 호.

Presentation on theme: "자료구조: CHAP 4 리스트 (3) 2017. 5. 2 순천향대학교 컴퓨터공학과 하 상 호."— Presentation transcript:

1 자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호

2 목차 리스트 추상 데이터 타입 배열로 구현된 리스트 단순 연결 리스트 원형 연결리스트 이중 연결리스트

3 원형 연결 리스트 연결 리스트에서 마지막 노드가 첫번째 노드를 가리키게 한다. 이점: 한 노드에서 임의 노드로 접근 가능
삽입, 삭제 연산 고려 head NULL …

4 삽입 연산: 원형 연결 리스트 첫번째 노드로 삽입
head NULL … node procedure insert_first(head: nodeptr, node: nodeptr) // head: 헤드 포인터 // node: 삽입될 노드

5 삽입 연산: 원형 연결 리스트 head NULL … node

6 삽입 연산: 원형 연결 리스트 마지막 노드로 삽입(self)
node head NULL … procedure insert_last(head: nodeptr, node: nodeptr) // head: 헤드 포인터 // node: 삽입될 노드

7 원형 연결 리스트 수정 헤드 포인터가 첫번째가 아닌 마지막 노드를 가리키게 변경하면? head NULL …

8 삽입 연산: 수정 원형 연결 리스트 첫번째 노드로 삽입(헤드가 첫번째 노드가리키는 경우와 비교)
head NULL … node procedure insert_first(head: nodeptr, node: nodeptr) // head: 헤드 포인터 // node: 삽입될 노드

9 삽입 연산: 수정 원형 연결 리스트 마지막 번째 노드로 삽입
node 마지막 번째 노드로 삽입 head NULL … procedure insert_last(head: nodeptr, node: nodeptr) // head: 헤드 포인터 // node: 삽입될 노드

10 display: 수정 원형 연결 리스트 procedure display(head: nodeptr) // 수정 필요
NULL … procedure display(head: nodeptr) // 수정 필요 // head: 헤드 포인터 // 리스트에 포함된 모든 노드 방문

11 질문 단순 연결 리스트나 원형 연결 리스트 상에서 특정 노드에서 선행 노드를 찾고자 한다면?
삽입, 삭제시에 반드시 선행 노드가 필요함 헤드포인터 10 20 NULL 30 50 40 head NULL …

12 이중 연결 리스트 노드가 선행 노드와 후속 노드에 대한 각각의 링크를 갖는 리스트
노드 구조: (llink, data, rlink) llink data rlink typedef int element; typedef struct node node; typedef node* nodeptr; typedef struct node { element data; nodeptr llink; nodeptr rlink; } node;

13 헤더 노드 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 특별한 노드
공백상태에서는 헤드 노드만 존재 헤드 포인터와 같은 역할 마지막 노드 삽입, 삭제시 효율적 p = p.llink.rlink = p.rlink.llink 헤드 노드 p

14 삽입 연산: 이중 연결 리스트 procedure dinsert_node(before: nodeptr, new: nodeptr)
(1) (2) (3) (4) before new_node procedure dinsert_node(before: nodeptr, new: nodeptr) // before: 이전 노드 // node: 삽입될 노드

15 삭제 연산: 이중 연결 리스트 removed procedure ddelete_node(head: nodeptr, removed: nodeptr) // head: 헤더 노드 // removed: 삭제될 노드

16 10주차 실습 과제 (due 5/10) 프로그램 4.29를 이해하여 다음을 수행하시오.
수업에서 정의한 node, nodeptr의 타입을 이용할 것 ‘*’의 타입 연산자가 나타나지 않게 할 것 …