리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센

Similar documents
슬라이드 1

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ

Microsoft PowerPoint - chap4_list

슬라이드 1

슬라이드 1

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

Microsoft PowerPoint - 06-List.ppt

1장. 리스트

4장

슬라이드 1

슬라이드 1

슬라이드 1

슬라이드 1

06장.리스트

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

C 언어 강의노트

11장 포인터

chap 5: Trees

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

Chapter 4. LISTS

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

슬라이드 1

Algorithms

Lab 3. 실습문제 (Single linked list)_해답.hwp

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

Chapter 4. LISTS

Chapter 4. LISTS

중간고사 (자료 구조)

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt

슬라이드 1

03_queue

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

PowerPoint 프레젠테이션

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

untitled

Microsoft PowerPoint - 자료구조2008Chap06

슬라이드 1

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

Microsoft PowerPoint - ch07 - 포인터 pm0415

01_List

chap 5: Trees

Chap 6: Graphs

슬라이드 1

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

PowerPoint Template

Microsoft PowerPoint - 07-chap05-Stack.ppt

슬라이드 1

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

Microsoft PowerPoint - 제4장-스택과큐.pptx

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - chap11-포인터의활용.pptx

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

Microsoft PowerPoint - chap06-2pointer.ppt

Microsoft PowerPoint - ch08_큐 [호환 모드]

PowerPoint Presentation

설계란 무엇인가?

설계란 무엇인가?

Microsoft PowerPoint - 8ÀÏ°_Æ÷ÀÎÅÍ.ppt

Microsoft PowerPoint - Chap5 [호환 모드]

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문

슬라이드 1

11장 포인터

03장.스택.key

슬라이드 1

PowerPoint Presentation

03장.스택

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

chap01_time_complexity.key

Microsoft PowerPoint 자바-기본문법(Ch2).pptx

슬라이드 1

Microsoft PowerPoint - 제3장-배열.pptx

JAVA PROGRAMMING 실습 08.다형성

02장.배열과 클래스

7장

Microsoft PowerPoint - Chapter14_17.pptx

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

Microsoft PowerPoint - Lesson14.pptx

Microsoft PowerPoint - Lesson14.pptx

08장.트리

Chap 6: Graphs

05_tree

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt

금오공대 컴퓨터공학전공 강의자료

슬라이드 1

Microsoft PowerPoint - 제8장-트리.pptx

BMP 파일 처리

Microsoft Word - FunctionCall

PowerPoint Presentation

Transcription:

Linked List 2014 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트 Lecture 03_Linkedlist 2 1

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센다 (count). 리스트가비었는지 (empty), 꽉찼는지 (full) 를체크. 리스트안의모든항목을표시. Lecture 03_Linkedlist 3 리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Linkedlist 4 2

배열을이용한구현 a b c a b c 연결리스트를이용한구현 a b c 2. 배열로구현한리스트 1 차원배열에항목들을순서대로저장 L=(A, B, C, D, E) L[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E 삽입연산 : 삽입위치다음의항목들을이동하여야함. N 0 1 2 3 4 5 6 7 8 9 A B C D E Lecture 03_Linkedlist 6 3

삭제연산 : 삭제위치다음의항목들을이동하여야함 0 1 2 3 4 5 6 7 8 9 A B C D E 0 1 2 3 4 5 6 7 8 9 A B C D E 0 1 2 3 4 5 6 7 8 9 A B D E Lecture 03_Linkedlist 7 N 0 1 2 3 4 5 0 1 2 3 4 5 A B C D E A B C D E A B C D E C A B D E A B C D E A B D E A B C D E A B D E A B N C D E Lecture 03_Linkedlist 8 4

배열을이용한리스트구현 list 1 차원배열에항목들을차례대로저장 length 에항목의개수저장 typedef struct { int list[max_list_size]; // 배열정의 int length; // 배열에저장된항목들의개수 ArrayListType; ArrayListType [0] [MAX_LIST_SIZE] List length Lecture 03_Linkedlist 9 is_empty(), is_full() 연산의구현 // 리스트가비어있으면 1을반환, 그렇지않으면 0을반환 int is_empty(arraylisttype *L) { return L->length == 0; // 리스트가가득차있으면 1을반환, 그렇지많으면 1을반환 int is_full(arraylisttype *L) { return L->length == MAX_LIST_SIZE; L->length L [0] [MAX_LIST_SIZE] ArrayListType length Lecture 03_Linkedlist 10 5

삽입연산 : add() 함수 배열이포화상태인지를검사, 삽입위치가적합한범위에있는지를검사. 삽입위치다음에있는자료들을한칸씩뒤로이동. // position: 삽입하고자하는위치, // item: 삽입하고자하는자료 void add(arraylisttype *L, int position, element item) { if(!is_full(l) && (position >= 0) && (position <= L->length) ){ int i; for(i=(l->length-1); i>=position;i--) L->list[i+1] = L->list[i]; L->list[position] = item; L->length++; Lecture 03_Linkedlist 11 삭제연산 : delete() 함수 삭제위치검사. 삭제위치부터맨끝까지의자료를한칸씩앞으로이동. // position: 삭제하고자하는위치 // 반환값 : 삭제되는자료 element delete(arraylisttype *L, int position) { int i; element item; if( position < 0 position >= L->length ) error(" 위치오류 "); item = L->list[position]; for(i=position; i<(l->length-1);i++) L->list[i] = L->list[i+1]; L->length--; return item; Lecture 03_Linkedlist 12 6

3. 연결리스트를이용한리스트구현 연결리스트 (linked list) 란? 일정한순서를가지는자료요소들을표현하는자료구조의한방법 자료요소들을통합하여관리함으로써정보의축적과탐색을효율적으로실현하기위해사용되는리스트구조 연결리스트표현 노드 (NODE) 구성 데이터 (data): 리스트의원소, 즉데이타값을저장하는곳 링크 (link): 다른노드의주소값을저장하는장소 ( 포인터 ) 데이터 링크 노드 (node) Lecture 03_Linkedlist 13 연결리스트의특징 연결리스트개념 리스트의항목들을노드 (node) 라고하는곳에분산하여저장 다음항목을가리키는주소도같이저장 노드 (node) : < 데이터, 링크 > 쌍 데이타필드 리스트의원소, 즉데이타값을저장하는곳 링크필드 다른노드의주소값을저장하는장소 ( 포인터 ) 메모리안에서의노드의물리적순서가리스트의논리적순서와일치할필요없음 Lecture 03_Linkedlist 14 7

연결리스트장점 삽입, 삭제가보다용이. 연속된메모리공간이필요없음. 크기제한이없음. 삽입연산 A B C D A B C D NEW Lecture 03_Linkedlist 15 연결리스트단점 구현이어렵다. 오류가발생하기쉽다 삭제연산 C A B D E Lecture 03_Linkedlist 16 8

헤드포인터 (head pointer) 리스트의첫번째노드를가리키는변수 헤드포인터 Stack area Heap Pointer A B C malloc( sizeof() ) C B malloc( sizeof() ) D Heap area A malloc( sizeof() ) Lecture 03_Linkedlist 17 노드생성과반환 필요할때마다동적메모리 (heap) 할당요구 ( malloc() ). 사용을마친노드반환 ( free() ) Stack area Heap Pointer C malloc( free() sizeof() ) B malloc( free() sizeof() ) Heap area A malloc( free() sizeof() ) Lecture 03_Linkedlist 18 9

연결리스트종류 단순연결리스트 (Simple Linked-List) 연결리스트의가장단순한형태 단방향성 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. Lecture 03_Linkedlist 19 이중연결리스트 (doubly linked list) 양방향으로노드들을탐색할수있음 각노드들은두개의링크를갖음 이전노드 다음노드 Lecture 03_Linkedlist 20 10

원형연결리스트 (circular linked list) 마지막노드의링크가첫번째노드를가리키는리스트 한노드에서다른모든노드로의접근이가능 헤드포인터 Lecture 03_Linkedlist 21 배열과연결리스트구현차이 연결리스트장점 삽입 / 삭제연산이위치에관계없이빠르게수행 무한개의자료저장 배열 : 고정된크기 연결리스트단점 순차접근, 불연속단위로저장 노드접근에긴지연시간 (delay time) 참조의지역성 (locality of reference) Lecture 03_Linkedlist 22 11

4. 단순연결리스트 단순연결리스트 (Simple Linked-List) 연결리스트의가장단순한형태 각노드들은오직하나의링크를갖기때문에 -> 단방향성. 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. 헤더 null 값을가리킬경우는빈리스트를나타냄 값을갖지않는다. Head Pointer 10 20 30 50 40 Lecture 03_Linkedlist 23 단순연결리스트구현 ( in C) 노드생성 데이터필드 : 구조체정의 링크필드 : 포인터 struct ListNode { int data; struct ListNode *link; ListNode; 노드의생성 : 동적메모리생성라이브러리 malloc 함수이용 ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); Lecture 03_Linkedlist 24 12

ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); p1 data link ListNode o 데이터필드와링크필드설정 p1->data = 10; p1->link = ; Stack area p1 p1 data 10 link Heap area 10 malloc( sizeof() ) 두번째노드생성과첫번째노드연결. ListNode *p2; p2 = (ListNode *)malloc(sizeof(listnode)); p2->data = 20; p2->link = ; p1->link = p2; p1 p2 data 10 link data link 20 Lecture 03_Linkedlist 26 13

단순연결리스트의삽입연산 before after 10 30 new 20 before after 10 30 20 new Lecture 03_Linkedlist 27 삽입함수의프로토타입 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) phead : 헤드포인터에대한포인터 p : 삽입될위치의선행노드를가리키는포인터, 이노드다음에삽입. new_node : 새로운노드를가리키는포인터 삽입의 3 가지경우 head 가 인경우 : 공백리스트에삽입 p 가 인경우 : 리스트의맨처음에삽입 일반적인경우 : 리스트의중간에삽입 Lecture 03_Linkedlist 28 14

phead head head p p new_node new_node Head 포인터가 인경우? 삽입노드가첫번째노드. head 의값만변경. if( *phead == ){ // 공백리스트인경우 new_node->link = ; *phead = new_node; head data link new_node Lecture 03_Linkedlist 30 15

p 가 인경우?? 새로운노드를리스트의맨앞에삽입 if( p == ) { // p가 이면첫번째노드로삽입 new_node->link = *phead; *phead = new_node; head new_node Lecture 03_Linkedlist 31 phead p head p *phead = new_node; head new_node new_node->link = *phead new_node Lecture 03_Linkedlist 32 16

head 와 p 가 이아닌경우?? (1) new_node 의 link 에 p->link 값을복사. (2) p->link 가 new_node 를가리키도록함. else { // p 다음에삽입 new_node->link = p->link; // (1) p->link = new_node; // (2) p head (2) (1) new_node Lecture 03_Linkedlist 33 // phead: 리스트의헤드포인터의포인터 // p : 선행노드 // new_node : 삽입될노드 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) { if( *phead == ){ // 공백리스트인경우 new_node->link = ; *phead = new_node; else if( p == ){ // p 가 이면첫번째노드로삽입 new_node->link = *phead; *phead = new_node; else { // p 다음에삽입 new_node->link = p->link; p->link = new_node; Lecture 03_Linkedlist 34 17

단순연결리스트의삭제 before removed after 10 20 30 before removed after 10 20 30 free(removed) Lecture 03_Linkedlist 35 삭제함수의프로토타입 void remove_node(listnode **phead, ListNode *p, ListNode *removed) phead: 헤드포인터의포인터 p: 삭제될노드의선행노드를가리키는포인터 removed: 삭제될노드를가리키는포인터 삭제의 2 가지경우 p 가 인경우 : 맨앞의노드를삭제 p 가 이아닌경우 : 중간노드를삭제 Lecture 03_Linkedlist 36 18

p 가 인경우?? 연결리스트의첫번째노드를삭제. 헤드포인터변경. if( p == ) *phead = (*phead)->link; head p Lecture 03_Linkedlist 37 p 가 이아닌경우?? removed 앞의노드인 p 의링크가 removed 다음노드를가리키도록변경 else p->link = removed->link; free(removed); p head removed Lecture 03_Linkedlist 38 19

// phead : 헤드포인터에대한포인터 // p: 삭제될노드의선행노드 // removed: 삭제될노드 void remove_node (ListNode **phead, ListNode *p, ListNode *removed) { if( p == ) *phead = (*phead)->link; else p->link = removed->link; free(removed) ; Lecture 03_Linkedlist 39 단순연결리스트의방문연산 방문연산 리스트상의노드를순차적으로방문 반복과순환기법을모두사용가능 반복버젼 void display(listnode *head) { ListNode *p=head; while( p!= ){ printf("%d->", p->data); p = p->link; printf("\n"); Lecture 03_Linkedlist 40 20

순환버젼 void display_recur(listnode *head) { ListNode *p=head; if( p!= ){ printf("%d->", p->data); display_recur(p->link); Lecture 03_Linkedlist 41 단순연결리스트의탐색연산 탐색연산 특정한데이터값을갖는노드를찾는연산 ListNode *search( ListNode *head, int x ) { ListNode *p; p = head; while( p!= ){ if( p->data == x ) return p; // 성공 return p; p = p->link; // 탐색실패일경우 반환 head p Lecture 03_Linkedlist 42 21

단순연결리스트의합병연산 합병연산 2 개의리스트를합하는연산 head1 head2 Lecture 03_Linkedlist 43 ListNode *concat(listnode *head1, ListNode *head2) { ListNode *p; if( head1 == ) return head2; else if( head2 == ) return head1; else { p = head1; while( p->link!= ) p = p->link; p->link = head2; return head1; Lecture 03_Linkedlist 44 22

단순연결리스트구현 ( in Java) 단순연결리스트 (Simple Linked-List) 연결리스트의가장단순한형태 각노드들은오직하나의링크를갖기때문에하나의노드만을가리킨다. -> 단방향성 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. 헤더 null 값을가리킬경우는빈리스트를나타냄 값을갖지않는다. Lecture 03_Linkedlist 45 노드구조 class LinkNode { private int idata; // 자료 ( 키 ) private LinkNode nodenext; // 다음노드포인터 // 생성자 public LinkNode( int idatainput ) { idata = idatainput; idata nodenext LinkNode Lecture 03_Linkedlist 46 23

LinkNode 주요메소드 class LinkNode { public void displaynode() { // 자료를출력메소드 System.out.print( idata ); public int getdata() { // 자료에접근메소드 return idata; public void setdata( int inputdata ) { // 자료변경메소드 idata = inputdata; public LinkNode getnodenext() { // 다음노드에접근하는메소드 return nodenext; // 다음노드참조자를변경하는메소드 public void setnodenext( LinkNode inputnode ) { nodenext = inputnode; Lecture 03_Linkedlist 47 insertfirst() 메소드 insertfirst() 새로운노드를리스트의가장첫번째자리에삽입하는메소드 a) 2 를삽입하기전의리스트 b) 2 를삽입한후의리스트 Lecture 03_Linkedlist 48 24

public void insertfirst( int ikey ) { // 새로운노드생성 LinkNode nodenew = new LinkNode(iKey); // 새로운노드는기존의첫번째노드를참조 nodenew.setnodenext( HeaderNode.getNodeFirst() ) ; // 헤더는새로운노드를참조 HeaderNode.setNodeFirst( nodenew ); Lecture 03_Linkedlist 49 deletefirst() 메소드 deletefirst() 리스트의첫번째노드를삭제하는역할을수행 a) 3 을삭제하기전의리스트 b) 3 을삭제한후의리스트 Lecture 03_Linkedlist 50 25

public LinkNode deletefirst() { // 빈리스트인지확인 if (HeaderNode.isEmpty() == false) { LinkNode tempnode = HeaderNode.getNodeFirst(); // 헤더는두번째노드를참조 HeaderNode.setNodeFirst ( HeaderNode.getNodeFirst().getNodeNext() ); return tempnode; // 삭제된노드를반환 else return null; // 빈리스트라면 null값반환 Lecture 03_Linkedlist 51 findnode() 메소드 findnode() 리스트내에서특정자료를갖고있는노드를찾는메소드 public LinkNode findnode( int ikey ) { // 리스트의첫번째노드부터탐색 LinkNode current = HeaderNode.getNodeFirst(); // 키값을탐색 while (current.getdata()!= ikey) { current = current.getnodenext(); // 다음노드검색. return current; // 키값갖고있는노드를반환 Lecture 03_Linkedlist 52 26

displaylist() 메소드 displaylist() 메소드 리스트로연결되어있는모든자료들즉, 각노드에저장되어있는자료들을출력하는메소드 public void displaylist() { // 리스트의첫번째노드부터출력 LinkNode current = HeaderNode.getNodeFirst(); while (current!= null) { current.displaynode(); // 노드자료출력 System.out.println(""); current = current.getnodenext(); // 다음노드탐색 Lecture 03_Linkedlist 53 insertnode() 메소드 insertnode() 리스트에새로운노드를특정위치에삽입하는메소드 a) 8 을삽입하기전의리스트 b) 8 을삽입한후의리스트 Lecture 03_Linkedlist 54 27

public void insertnode( int ikey ) { // 새로운노드생성 LinkNode nodenew = new LinkNode( ikey ); // 첫번째노드부터검색 LinkNode current = HeaderNode.getNodeFirst(); LinkNode previous = null; // 빈리스트가아니고, 마지막노드도아니며, 새로운키값이더클경우, while (current!= null && ikey > current.getdata()) { previous = current; current = current.getnodenext(); if (previous == null) // 빈리스트, 새로운노드를첫번째자리로삽입 HeaderNode.setNodeFirst( nodenew ); else // 이전노드참조자가새로운노드를가리키도록변경 previous.setnodenext( nodenew ); // 새로운노드의다음노드참조자를현재노드를기리키도록변경 nodenew.setnodenext( current ); Lecture 03_Linkedlist 55 deletenode() 메소드 deletenode() 리스트에서특정노드를검색한후삭제하는메소드 a) 8 을삭제하기전의리스트 b) 8 을삭제한후의리스트 Lecture 03_Linkedlist 56 28

public LinkNode deletenode( int ikey ) { // 첫번째노드부터검색 LinkNode current = HeaderNode.getNodeFirst(); LinkNode previous = null; // 빈리스트가아니고, 마지막노드도아니며, 찾는키값이아닐경우, while (current!= null && ikey!= current.getdata()) { previous = current; current = current.getnodenext(); // 빈리스트 & 마지막노드가아닌경우, 포인터변경하고삭제된노드반환 if (previous!= null && current!= null) { previous.setnodenext( current.getnodenext() ); else if (previous == null && current!= null) { HeaderNode.setNodeFirst( current.getnodenext() ); return current; Lecture 03_Linkedlist 57 이중말단연결리스트 (Double-Ended Linked-List) 개념 단순연결리스트와유사한구조 헤더가첫번째노드뿐만아니라마지막노드를가리키는포인터를함께갖고있음 Lecture 03_Linkedlist 58 29

감시노드 class LinkSentinelNode { private LinkNode nodefirst; private LinkNode nodelast; // 첫번째노드를참조 // 마지막노드를참조 // 생성자 public LinkSentinelNode() { nodefirst = null; nodelast = null; // 첫번째노드를참조하는포인터접근메소드 public LinkNode getnodefirst() { return nodefirst; Lecture 03_Linkedlist 59 class LinkSentinelNode { // 첫번째노드를참조하는포인터변경메소드 public void setnodefirst( LinkNode inputnode ) { nodefirst = inputnode; // 마지막노드를참조하는포인터접근메소드 public LinkNode getnodelast() { return nodelast; // 마지막노드를참조하는포인터변경메소드 public void setnodelast( LinkNode inputnode ) { nodelast = inputnode; // 빈리스트인지확인하는메소드 public boolean isempty() { return (nodefirst == null); Lecture 03_Linkedlist 60 30

insertnode() public void insertnode( int ikey ) { // 새로운노드생성 LinkNode nodenew = new LinkNode( ikey ); // 첫번째노드부터검색 LinkNode current = HeaderNode.getNodeFirst(); LinkNode previous = null; // 빈리스트 & 마지막노드도아니며, 새로운키값이더클경우, while (current!= null && ikey > current.getdata()) { previous = current; current = current.getnodenext(); // 빈리스트일경우 if (HeaderNode.isEmpty() == true) { // 새로운노드를첫번째자리로삽입 HeaderNode.setNodeFirst( nodenew ); HeaderNode.setNodeLast( nodenew ); Lecture 03_Linkedlist 61 // 새로운노드를첫번째자리로삽입 else if (HeaderNode.getNodeFirst() == current) { HeaderNode.setNodeFirst( nodenew ); // 새로운노드를마지막자리로삽입 else if (current == null) { previous.setnodenext( nodenew ); HeaderNode.setNodeLast( nodenew ); // 새로운노드를중간에삽입 else previous.setnodenext( nodenew ); nodenew.setnodenext( current ); Lecture 03_Linkedlist 62 31

deletenode() public LinkNode deletenode( int ikey ) { LinkNode current = HeaderNode.getNodeFirst(); LinkNode previous = null; // 빈리스트 & 마지막노드도아니며, 찾는키값이아닐경우 while(current!= null && ikey!= current.getdata()) { previous = current; current = current.getnodenext(); // 첫번째노드를삭제할경우 if (HeaderNode.getNodeFirst() == current) { if (HeaderNode.getNodeFirst() == HeaderNode.getNodeLast()) { HeaderNode.setNodeFirst( null ); HeaderNode.setNodeLast( null ); else HeaderNode.setNodeFirst( current.getnodenext() ); Lecture 03_Linkedlist 63 else if (HeaderNode.getNodeLast() == current) { previous.setnodenext( null ); HeaderNode.setNodeLast( previous ); // 중간노드를삭제할경우 else { previous.setnodenext( current.getnodenext()); // 삭제된노드를반환 return current; Lecture 03_Linkedlist 64 32

displaylastnode() public void displaylastnode() { HeaderNode.getNodeLast().displayNode(); System.out.println(""); Lecture 03_Linkedlist 65 5. 이중연결리스트 (doubly linked list) 개념 노드가선행노드와후속노드에대한두개의링크를가지는리스트 링크가양방향이므로양방향으로검색이가능 공간을많이차지하고코드가복잡 실제사용되는이중연결리스트의형태 헤드노드 + 이중연결리스트 + 원형연결리스트 헤드노드 Lecture 03_Linkedlist 66 33

헤드노드 (head node) 데이터를가지지않고단지삽입, 삭제코드를간단하게할목적으로만들어진노드 헤드포인터와의구별필요 공백상태에서는헤드노드만존재 이중연결리스트의노드구조 typedef struct DlistNode { int data; struct DlistNode *llink; struct DlistNode *rlink; DlistNode; llink data rlink Lecture 03_Linkedlist 67 삽입연산 before (1) new_node->llink = before; (2) new_node->rlink = before ->rlink; (4) before->rlink = new_node; (3) before->rlink->llink = new_node ; new_node Lecture 03_Linkedlist 68 34

// 노드 new_node를노드 before의오른쪽에삽입한다. void dinsert_node(dlistnode *before, DlistNode *new_node) { new_node->llink = before; // 1) new_node->rlink = before->rlink; // 2) before->rlink->llink = new_node; // 3) before->rlink = new_node; // 4) Lecture 03_Linkedlist 69 삭제연산 before (1) removed->llink->rlink = removed->rlink; (2) removed ->rlink->llink = removed ->llink; removed Lecture 03_Linkedlist 70 35

// 노드 removed를삭제한다. void dremove_node(dlistnode *phead_node, DlistNode *removed) { if( removed == phead_node ) return; removed->llink->rlink = removed->rlink; // 1) removed->rlink->llink = removed->llink; // 2) free(removed); Lecture 03_Linkedlist 71 p = p->llink->rlink = p->rlink->llink 100 번지 200 번지 300 번지 200 300 llink rlink llink rlink llink rlink 100 200 p Lecture 03_Linkedlist 72 36

이중연결리스트 insertfirst() insertnode() 메소드 일반노드추가시 nodeprevious 참조자를위한과정이추가 nodenext 와 nodeprevious 가다음노드와이전노드를참조하는참조자의역할 Lecture 03_Linkedlist 73 public void insertnode( int ikey ) { // 새로운노드생성 LinkNode nodenew = new LinkNode( ikey ); // 첫번째노드부터검색 LinkNode current = HeaderNode.getNodeFirst(); LinkNode previous = null; // 마지막노드도아니며, 새로운키값이더클경우, while (current!= null && ikey > current.getdata()) { previous = current; current = current.getnodenext(); Lecture 03_Linkedlist 74 37

// 빈리스트일경우 if (HeaderNode.isEmpty() == true) { // 새로운노드를첫번째자리로삽입 HeaderNode.setNodeFirst( nodenew ); nodenew.setnodenext( null ); nodenew.setnodeprevious( null ); // 새로운노드를첫번째자리로삽입 else if (HeaderNode.getNodeFirst() == current) { nodenew.setnodenext( HeaderNode.getNodeFirst() ); HeaderNode.setNodeFirst( nodenew ); nodenew.setnodeprevious( null ); Lecture 03_Linkedlist 75 // 새로운노드를마지막자리로삽입 else if (current == null) { previous.setnodenext( nodenew ); nodenew.setnodeprevious( previous ); nodenew.setnodenext( null ); // 새로운노드를중간에삽입 else { nodenew.setnodenext( previous.getnodenext() ); previous.setnodenext( nodenew ); nodenew.setnodeprevious( previous ); nodenew.getnodenext().setnodeprevious( nodenew ); Lecture 03_Linkedlist 76 38

이중연결리스트 deletenode() deletenode() 메소드 nodeprevious 참조자 public LinkNode deletenode( int ikey ) { // 첫번째노드부터검색 LinkNode current = HeaderNode.getNodeFirst(); LinkNode previous = null; // 빈리스트, 마지막노드, 찾는키값이아닐경우, while (current!= null && ikey!= current.getdata()) { previous = current; current = current.getnodenext(); Lecture 03_Linkedlist 77 // 첫번째노드를삭제할경우 if (HeaderNode.getNodeFirst() == current) { HeaderNode.setNodeFirst( current.getnodenext() ); // 마지막노드를삭제할경우 else if (current.getnodenext() == null) { previous.setnodenext( null ); // 중간노드를삭제할경우 else { previous.setnodenext( current.getnodenext() ); current.getnodenext().setnodeprevious( previous ); // 삭제된노드를반환 return current; Lecture 03_Linkedlist 78 39

6. 원형연결리스트 원형연결리스트 (Circular linked list) 마지막노드의링크가첫번째노드를가리키는리스트 한노드에서다른모든노드로의접근이가능 head 보통헤드포인터가마지막노드를가리키게끔구성하면리스트의처음이나마지막에노드를삽입하는연산이단순연결리스트에비하여용이 head Lecture 03_Linkedlist 79 원형연결리스트의처음에삽입 (2) A B C D (1) E head node Lecture 03_Linkedlist 80 40

// phead: 리스트의헤드포인터의포인터 // p : 선행노드, // node : 삽입될노드 void insert_first(listnode **phead, ListNode *node) { if( *phead == ) { *phead = node; node->link = node; else { node->link = (*phead)->link; (*phead)->link = node; Lecture 03_Linkedlist 81 원형연결리스트의끝에삽입 (2) A B C D (1) (3) E head node Lecture 03_Linkedlist 82 41

// phead: 리스트의헤드포인터의포인터 // p : 선행노드, // node : 삽입될노드 void insert_last(listnode **phead, ListNode *node) { if( *phead == ){ *phead = node; node->link = node; else { node->link = (*phead)->link; (*phead)->link = node; *phead = node; Lecture 03_Linkedlist 83 42