슬라이드 1

Transcription

1 Linked List 학기 SANGJI University

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

3 리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센다 (count). 리스트가비었는지 (empty), 꽉찼는지 (full) 를체크. 리스트안의모든항목을표시. Linkedlist 3

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

5 배열을이용한구현 a b c a b c 연결리스트를이용한구현 a b c NULL

6 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 A B C D E Linkedlist 6

7 삭제연산 : 삭제위치다음의항목들을이동하여야함 A B C D E A B C D E A B D E Linkedlist 7

8 N 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 Linkedlist 8

9 배열을이용한리스트구현 list 1차원배열에항목들을차례대로저장 length에항목의개수저장 typedef struct { int list[max_list_size]; // 배열정의 int length; // 배열에저장된항목들의개수 ArrayListType; ArrayListType [0] [MAX_LIST_SIZE] List length Linkedlist 9

10 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 Linkedlist 10

11 삽입연산 : 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++; Linkedlist 11

12 삭제연산 : 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; Linkedlist 12

13 3. 연결리스트를이용한리스트구현 연결리스트 (linked list) 란? 일정한순서를가지는자료요소들을표현하는자료구조의한방법 자료요소들을통합하여관리함으로써정보의축적과탐색을효율적으로실현하기위해사용되는리스트구조 연결리스트표현 노드 (NODE) 구성 데이터 (data): 리스트의원소, 즉데이타값을저장하는곳 링크 (link): 다른노드의주소값을저장하는장소 ( 포인터 ) 데이터 링크 노드 (node) Linkedlist 13

14 연결리스트의특징 연결리스트개념 리스트의항목들을노드 (node) 라고하는곳에분산하여저장 다음항목을가리키는주소도같이저장 노드 (node) : < 데이터, 링크 > 쌍 데이타필드 리스트의원소, 즉데이타값을저장하는곳 링크필드 다른노드의주소값을저장하는장소 ( 포인터 ) 메모리안에서의노드의물리적순서가리스트의논리적순서와일치할필요없음 Linkedlist 14

15 연결리스트장점 삽입, 삭제가보다용이. 연속된메모리공간이필요없음. 크기제한이없음. 삽입연산 A B C D A B C D NEW Linkedlist 15

16 연결리스트단점 구현이어렵다. 오류가발생하기쉽다 삭제연산 C A D E B Linkedlist 16

17 헤드포인터 (head pointer) 리스트의첫번째노드를가리키는변수 헤드포인터 Stack area Heap Pointer A B C malloc( sizeof() ) C D Heap area B A malloc( sizeof() ) malloc( sizeof() ) Linkedlist 17

18 노드생성과반환 필요할때마다동적메모리 (heap) 할당요구 ( malloc() ). 사용을마친노드반환 ( free() ) Stack area Heap Pointer C malloc( free() sizeof() ) B malloc( free() sizeof() ) Heap area A malloc( free() sizeof() ) Linkedlist 18

19 연결리스트종류 단순연결리스트 (Simple Linked-List) 연결리스트의가장단순한형태 단방향성 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. Linkedlist 19

20 이중연결리스트 (doubly linked list) 양방향으로노드들을탐색할수있음 각노드들은두개의링크를갖음 이전노드 다음노드 Linkedlist 20

21 원형연결리스트 (circular linked list) 마지막노드의링크가첫번째노드를가리키는리스트 한노드에서다른모든노드로의접근이가능 헤드포인터 Linkedlist 21

22 연결리스트장점 배열과연결리스트구현차이 삽입 / 삭제연산이위치에관계없이빠르게수행 무한개의자료저장 배열 : 고정된크기 연결리스트단점 순차접근, 불연속단위로저장 노드접근에긴지연시간 (delay time) 참조의지역성 (locality of reference) Linkedlist 22

23 4. 단순연결리스트 단순연결리스트 (Simple Linked-List) 연결리스트의가장단순한형태 각노드들은오직하나의링크를갖기때문에 -> 단방향성. 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. 헤더 null 값을가리킬경우는빈리스트를나타냄 값을갖지않는다. Head Pointer NULL NULL NULL Linkedlist 23

24 노드생성 단순연결리스트구현 ( in C) 데이터필드 : 구조체정의 링크필드 : 포인터 struct ListNode { int data; struct ListNode *link; ListNode; 노드의생성 : 동적메모리생성라이브러리 malloc 함수이용 ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); Linkedlist 24

25 ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); p1 data link ListNode 데이터필드와링크필드설정 p1->data = 10; p1->link = NULL; Stack area p1 p1 data 10 link NULL Heap area 10 malloc( sizeof() )

26 두번째노드생성과첫번째노드연결. ListNode *p2; p2 = (ListNode *)malloc(sizeof(listnode)); p2->data = 20; p2->link = NULL; p1->link = p2; p1 p2 data 10 link NULL data link 20 NULL Linkedlist 26

27 단순연결리스트의삽입연산 before after new 20 before after new Linkedlist 27

28 삽입함수의프로토타입 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) phead : 헤드포인터에대한포인터 p : 삽입될위치의선행노드를가리키는포인터, 이노드다음에삽입. new_node : 새로운노드를가리키는포인터 삽입의 3 가지경우 head가 NULL인경우 : 공백리스트에삽입 p가 NULL인경우 : 리스트의맨처음에삽입 일반적인경우 : 리스트의중간에삽입 Linkedlist 28

29 phead head head p p NULL NULL new_node new_node NULL

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

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

32 phead head p p NULL *phead = new_node; head new_node new_node->link = *phead NULL new_node Linkedlist 32

33 head 와 p 가 NULL 이아닌경우?? (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 NULL (2) (1) new_node Linkedlist 33

34 // phead: 리스트의헤드포인터의포인터 // p : 선행노드 // new_node : 삽입될노드 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) { if( *phead == NULL ){ // 공백리스트인경우 new_node->link = NULL; *phead = new_node; else if( p == NULL ){ // p 가 NULL 이면첫번째노드로삽입 new_node->link = *phead; *phead = new_node; else { // p 다음에삽입 new_node->link = p->link; p->link = new_node; Linkedlist 34

35 단순연결리스트의삭제 before removed after before removed after free(removed) Linkedlist 35

36 삭제함수의프로토타입 void remove_node(listnode **phead, ListNode *p, ListNode *removed) phead: 헤드포인터의포인터 p: 삭제될노드의선행노드를가리키는포인터 removed: 삭제될노드를가리키는포인터 삭제의 2 가지경우 p 가 NULL 인경우 : 맨앞의노드를삭제 p 가 NULL 이아닌경우 : 중간노드를삭제 Linkedlist 36

37 p 가 NULL 인경우?? 연결리스트의첫번째노드를삭제. 헤드포인터변경. if( p == NULL ) *phead = (*phead)->link; head NULL p NULL Linkedlist 37

38 p 가 NULL 이아닌경우?? removed 앞의노드인 p 의링크가 removed 다음노드를가리키도록변경 else p->link = removed->link; free(removed); p head NULLNULL removed Linkedlist 38

39 // phead : 헤드포인터에대한포인터 // p: 삭제될노드의선행노드 // removed: 삭제될노드 void remove_node (ListNode **phead, ListNode *p, ListNode *removed) { if( p == NULL ) *phead = (*phead)->link; else p->link = removed->link; free(removed); Linkedlist 39

40 방문연산 단순연결리스트의방문연산 리스트상의노드를순차적으로방문 반복과순환기법을모두사용가능 반복버젼 void display(listnode *head) { ListNode *p=head; while( p!= NULL ){ printf("%d->", p->data); p = p->link; printf("\n"); Linkedlist 40

41 순환버젼 void display_recur(listnode *head) { ListNode *p=head; if( p!= NULL ){ printf("%d->", p->data); display_recur(p->link); Linkedlist 41

42 탐색연산 단순연결리스트의탐색연산 특정한데이터값을갖는노드를찾는연산 ListNode *search( ListNode *head, int x ) { ListNode *p; p = head; while( p!= NULL ){ if( p->data == x ) return p; // 성공 return p; p = p->link; // 탐색실패일경우 NULL 반환 head NULL NULL NULL p Linkedlist 42

43 합병연산 단순연결리스트의합병연산 2 개의리스트를합하는연산 head1 NULL NULL NULL head2 NULL NULL NULL Linkedlist 43

44 ListNode *concat(listnode *head1, ListNode *head2) { ListNode *p; if( head1 == NULL ) return head2; else if( head2 == NULL ) return head1; else { p = head1; while( p->link!= NULL ) p = p->link; p->link = head2; return head1; Linkedlist 44

45 단순연결리스트구현 ( in Java) 단순연결리스트 (Simple Linked-List) 연결리스트의가장단순한형태 각노드들은오직하나의링크를갖기때문에하나의노드만을가리킨다. -> 단방향성 마지막노드의링크 헤더 null 값을가리킬경우는리스트의끝을나타냄. null 값을가리킬경우는빈리스트를나타냄 값을갖지않는다. Linkedlist 45

46 노드구조 class LinkNode { private int idata; // 자료 ( 키 ) private LinkNode nodenext; // 다음노드포인터 // 생성자 public LinkNode( int idatainput ) { idata = idatainput; idata nodenext LinkNode Linkedlist 46

47 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; Linkedlist 47

48 insertfirst() insertfirst() 메소드 새로운노드를리스트의가장첫번째자리에삽입하는메소드 a) 2 를삽입하기전의리스트 b) 2 를삽입한후의리스트 Linkedlist 48

49 public void insertfirst( int ikey ) { // 새로운노드생성 LinkNode nodenew = new LinkNode(iKey); // 새로운노드는기존의첫번째노드를참조 nodenew.setnodenext( HeaderNode.getNodeFirst() ) ; // 헤더는새로운노드를참조 HeaderNode.setNodeFirst( nodenew ); Linkedlist 49

50 deletefirst() deletefirst() 메소드 리스트의첫번째노드를삭제하는역할을수행 a) 3 을삭제하기전의리스트 b) 3 을삭제한후의리스트 Linkedlist 50

51 public LinkNode deletefirst() { // 빈리스트인지확인 if (HeaderNode.isEmpty() == false) { LinkNode tempnode = HeaderNode.getNodeFirst(); // 헤더는두번째노드를참조 HeaderNode.setNodeFirst ( HeaderNode.getNodeFirst().getNodeNext() ); return tempnode; // 삭제된노드를반환 else return null; // 빈리스트라면 null값반환 Linkedlist 51

52 findnode() findnode() 메소드 리스트내에서특정자료를갖고있는노드를찾는메소드 public LinkNode findnode( int ikey ) { // 리스트의첫번째노드부터탐색 LinkNode current = HeaderNode.getNodeFirst(); // 키값을탐색 while (current.getdata()!= ikey) { current = current.getnodenext(); // 다음노드검색. return current; // 키값갖고있는노드를반환 Linkedlist 52

53 displaylist() 메소드 displaylist() 메소드 리스트로연결되어있는모든자료들즉, 각노드에저장되어있는자료들을출력하는메소드 public void displaylist() { // 리스트의첫번째노드부터출력 LinkNode current = HeaderNode.getNodeFirst(); while (current!= null) { current.displaynode(); // 노드자료출력 System.out.println(""); current = current.getnodenext(); // 다음노드탐색 Linkedlist 53

54 insertnode() insertnode() 메소드 리스트에새로운노드를특정위치에삽입하는메소드 a) 8 을삽입하기전의리스트 b) 8 을삽입한후의리스트 Linkedlist 54

55 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 ); Linkedlist 55

56 deletenode() deletenode() 메소드 리스트에서특정노드를검색한후삭제하는메소드 a) 8 을삭제하기전의리스트 b) 8 을삭제한후의리스트 Linkedlist 56

57 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; Linkedlist 57

58 개념 이중말단연결리스트 (Double-Ended Linked-List) 단순연결리스트와유사한구조 헤더가첫번째노드뿐만아니라마지막노드를가리키는포인터를함께갖고있음 Linkedlist 58

59 감시노드 class LinkSentinelNode { private LinkNode nodefirst; private LinkNode nodelast; // 첫번째노드를참조 // 마지막노드를참조 // 생성자 public LinkSentinelNode() { nodefirst = null; nodelast = null; // 첫번째노드를참조하는포인터접근메소드 public LinkNode getnodefirst() { return nodefirst; Linkedlist 59

60 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); Linkedlist 60

61 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 ); Linkedlist 61

62 // 새로운노드를첫번째자리로삽입 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 ); Linkedlist 62

63 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() ); Linkedlist 63

64 else if (HeaderNode.getNodeLast() == current) { previous.setnodenext( null ); HeaderNode.setNodeLast( previous ); // 중간노드를삭제할경우 else { previous.setnodenext( current.getnodenext()); // 삭제된노드를반환 return current; Linkedlist 64

65 displaylastnode() public void displaylastnode() { HeaderNode.getNodeLast().displayNode(); System.out.println(""); Linkedlist 65

66 5. 이중연결리스트 (doubly linked list) 개념 노드가선행노드와후속노드에대한두개의링크를가지는리스트 링크가양방향이므로양방향으로검색이가능 공간을많이차지하고코드가복잡 실제사용되는이중연결리스트의형태 헤드노드 + 이중연결리스트 + 원형연결리스트 헤드노드 Linkedlist 66

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

68 삽입연산 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 Linkedlist 68

69 // 노드 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) Linkedlist 69

70 삭제연산 before (1) removed->llink->rlink = removed->rlink; (2) removed->rlink->llink = removed->llink; removed Linkedlist 70

71 // 노드 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); Linkedlist 71

72 p = p->llink->rlink = p->rlink->llink 100 번지 200 번지 300 번지 llink rlink llink rlink llink rlink p Linkedlist 72

73 이중연결리스트 insertfirst() insertnode() 메소드 일반노드추가시 nodeprevious 참조자를위한과정이추가 nodenext 와 nodeprevious 가다음노드와이전노드를참조하는참조자의역할 Linkedlist 73

74 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(); Linkedlist 74

75 // 빈리스트일경우 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 ); Linkedlist 75

76 // 새로운노드를마지막자리로삽입 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 ); Linkedlist 76

77 이중연결리스트 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(); Linkedlist 77

78 // 첫번째노드를삭제할경우 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; Linkedlist 78

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

80 원형연결리스트의처음에삽입 (2) A B NULL C NULL D (1) E head node Linkedlist 80

81 // phead: 리스트의헤드포인터의포인터 // p : 선행노드, // node : 삽입될노드 void insert_first(listnode **phead, ListNode *node) { if( *phead == NULL ) { *phead = node; node->link = node; else { node->link = (*phead)->link; (*phead)->link = node; Linkedlist 81

82 원형연결리스트의끝에삽입 (2) A B NULL C NULL D (1) (3) E head node Linkedlist 82

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