Chap. 4 : 리스트 (list) 2007 학년도 2 학기
리스트 1. 리스트개념 ~ 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 ~ 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 ~ 요일 : ( 일요일, 월요일,, 토요일 ) ~ 한글자음의모임 : (ᆨ,ᆫ,,ᄒ) ~ 핸드폰의문자메시지리스트 -2-
리스트연산 ~ 새로운항목을리스트의끝, 처음, 중간에추가. ~ 기존의항목을리스트의임의의위치에서삭제. ~ 모든항목을삭제. ~ 기존의항목을대치 (replace). ~ 리스트가특정한항목을가지고있는지를검색 (search). ~ 리스트의특정위치의항목을반환. ~ 리스트안의항목의개수를센다. ~ 리스트가비었는지, 꽉찼는지를체크. ~ 리스트안의모든항목을표시. -3-
리스트구현방법 배열 (array) 을이용하는방법 ~ 구현이간단 ~ 삽입, 삭제시오버헤드 삽입또는삭제동작에따른원소이동 ~ 항목의개수제한, 정적기억공간할당 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 ~ 구현이복잡 ~ 삽입, 삭제가효율적 ~ 크기가제한되지않음 -4-
배열을이용한구현 a b c a b c a b c NULL 연결리스트를이용한구현 -5-
2. 배열로구현한리스트 1 차원배열에항목들을순서대로저장 L=(A, B, C, D, E) 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 -6-
삭제연산 : 삭제위치다음의항목들을이동하여야함 C 0 1 2 3 4 5 6 7 8 9 A B D E -7-
N 0 1 2 3 4 5 A B C D E A B C D E 0 1 2 3 4 5 A B C D E C A B C D E A B D E A B C D E A B D E A B N C D E A B D E -8-
3. 연결리스트를이용한리스트구현 연결리스트 (linked list) 란? ~ 일정한순서를가지는자료요소들을표현하는자료구조의한방법 ~ 자료요소들을통합하여관리함으로써정보의축적과탐색을효율적으로실현하기위해사용되는리스트구조 연결리스트표현 ~ 데이터 (data) 와링크 (link) 로구성된노드 (NODE) 데이타필드 리스트의원소, 즉데이타값을저장하는곳 링크필드 다른노드의주소값을저장하는장소 ( 포인터 ) 데이터 링크 노드 (node) -9-
연결리스트의특징 3.1 연결리스트개념 ~ 리스트의항목들을노드 (node) 라고하는곳에분산하여저장 ~ 다음항목을가리키는주소도같이저장 ~ 노드 (node) : < 데이터, 링크 > 쌍 ~ 노드는데이타필드와링크필드로구성 데이타필드 리스트의원소, 즉데이타값을저장하는곳 링크필드 다른노드의주소값을저장하는장소 ( 포인터 ) ~ 메모리안에서의노드의물리적순서가리스트의논리적순서와일치할필요없음 -10-
연결리스트장점 (3.2 참고 ) ~ 삽입, 삭제가보다용이. ~ 연속된메모리공간이필요없음. ~ 크기제한이없음. 삽입연산 N A C D E B 메인메모리 -11-
연결리스트단점 (3.2 참고 ) ~ 구현이어렵다. ~ 오류가발생하기쉽다 삭제연산 A C D E B 메인메모리 -12-
노드 (node) ~ 데이터필드 + 링크필드 data link 헤드포인터 (head pointer) ~ 리스트의첫번째노드를가리키는변수 헤드포인터 NULL -13-
노드의생성 ~ 필요할때마다동적메모리이용하여노드생성 운영체제 요구 동적생성 헤드포인터 NULL -14-
연결리스트종류 단순연결리스트 (Simple Linked-List) ~ 연결리스트의가장단순한형태 ~ 각노드들은오직하나의링크를갖기때문에하나의노드만을가리킨다. -> 단방향성 ~ 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. ~ 헤더 null 값을가리킬경우는빈리스트를나타냄 값을갖지않는다. -15-
이중연결리스트 (doubly linked list) ~ 양방향으로노드들을탐색할수있음 ~ 각노드들은두개의링크를갖음 이전노드 다음노드 -16-
원형연결리스트 (circular linked list) 헤드포인터 ~ 마지막노드의링크가첫번째노드를가리키는리스트 ~ 한노드에서다른모든노드로의접근이가능 -17-
3.2 배열과연결리스트구현차이 연결리스트장점 ~ 삽입 / 삭제연산이위치에관계없이빠르게수행 ~ 무한개의자료저장 배열 : 고정된크기 연결리스트단점 ~ 순차접근, 불연속단위로저장 노드접근에긴지연시간 (delay time) ~ 참조의지역성 (locality of reference) 그림 4.4 참고 -18-
배열과연결리스트의복잡도비교 인덱싱 (indexing) ~ 리스트내에존재하는자료들중임의로하나선택하는연산 지역성 (locality) ~ 자료들이더당되는메모리에얼마만큼밀집해서저장되는가는의미 인덱싱자료삽입자료삭제지역성 배열 0(1) 0(n) 0(n) 좋다 연결리스트 0(n) 0(1) 0(1) 나쁘다 -19-
3.3 감시노드 감시노드 (sentinel node) ~ 리스트에가장첫번째자리에어떠한방식으로새로운자료를삽입할것인가하는문제 ~ 첫번째자리의자료를어떠한방식으로삭제할것인가하는문제 ~ 리스트를관리하기위한어떠한개체가있어야한다는문제. 헤더 (header) 노드, 더미 (dummy) 노드 ~ 첫번째원소를가리키는링크만유지. -20-
4. 단순연결리스트 단순연결리스트 (Simple Linked-List) ~ 연결리스트의가장단순한형태 ~ 각노드들은오직하나의링크를갖기때문에하나의노드만을가리킨다. -> 단방향성 ~ 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. ~ 헤더 null 값을가리킬경우는빈리스트를나타냄 값을갖지않는다. 헤드포인터 10 20 NULL 30 NULL 40 NULL 50 NULL -21-
단순연결리스트구현 ( in C) 노드생성 ~ 데이터필드 : 구조체로정의 ~ 링크필드 : 포인터사용 struct ListNode { int data; struct ListNode *link; ListNode; ~ 노드의생성 : 동적메모리생성라이브러리 malloc 함수이용 ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); -22-
ListNode *p1; p1 = (ListNode *)malloc(sizeof(listnode)); p1 data link ListNode 데이터필드와링크필드설정 p1->data = 10; p1->link = NULL; p1 10 NULL -23-
두번째노드생성과첫번째노드와의연결 ListNode *p2; p2 = (ListNode *)malloc(sizeof(listnode)); p2->data = 20; p2->link = NULL; p1->link = p2; p1 10 20 NULL -24-
단순연결리스트의삽입연산 before after 10 30 20 new insert_node(l,before,new) if L = NULL then L new else new.link before.link before.link new before 10 30 after 20 new -25-
삽입함수의프로토타입 void insert_node(listnode **phead, ListNode *p, ListNode *new_node) ~ phead : 헤드포인터 head 에대한포인터 ~ p : 삽입될위치의선행노드를가리키는포인터, 이노드다음에삽입. ~ new_node : 새로운노드를가리키는포인터 삽입의 3 가지경우 ~ head가 NULL인경우 : 공백리스트에삽입 ~ p가 NULL인경우 : 리스트의맨처음에삽입 ~ 일반적인경우 : 리스트의중간에삽입 -26-
phead p head p head NULL NULL new_node new_node NULL -27-
head 가 NULL 인경우 ~ 현재삽입하려는노드가첫번째노드. ~ head 의값만변경. if( *phead == NULL ){ // 공백리스트인경우 new_node->link = NULL; *phead = new_node; head new_node NULL -28-
p 가 NULL 인경우 ~ 새로운노드를리스트의맨앞에삽입 if( p == NULL ) { // p 가 NULL 이면첫번째노드로삽입 new_node->link = *phead; *phead = new_node; head NULL NULL new_node NULL -29-
head 와 p 가 NULL 이아닌경우 ~ new_node 의 link 에 p->link 값을복사. ~ p->link 가 new_node 를가리키도록함. else { // p 다음에삽입 new_node->link = p->link; p->link = new_node; p head NULL (2) (1) new_node -30-
// 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; -31-
단순연결리스트의삭제연산 before removed after 10 20 30 before removed after 10 20 30-32-
삭제함수의프로토타입 void remove_node(listnode **phead, ListNode *p, ListNode *removed) ~ phead: 헤드포인터 head 의포인터 ~ p: 삭제될노드의선행노드를가리키는포인터 ~ removed: 삭제될노드를가리키는포인터 삭제의 2 가지경우 ~ p 가 NULL 인경우 : 맨앞의노드를삭제 ~ p 가 NULL 이아닌경우 : 중간노드를삭제 -33-
p 가 NULL 인경우 ~ 연결리스트의첫번째노드를삭제. ~ 헤드포인터변경. if( p == NULL ) *phead = (*phead)->link; list NULL removed -34-
p 가 NULL 이아닌경우 ~ removed 앞의노드인 p 의링크가 removed 다음노드를가리키도록변경 else p->link = removed->link; free(removed); p list NULLNULL removed -35-
// 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); -36-
단순연결리스트의방문연산 방문연산 ~ 리스트상의노드를순차적으로방문 ~ 반복과순환기법을모두사용가능 반복버젼 void display(listnode *head) { ListNode *p=head; while( p!= NULL ){ printf("%d->", p->data); p = p->link; printf("\n"); -37-
순환버젼 void display_recur(listnode *head) { ListNode *p=head; if( p!= NULL ){ printf("%d->", p->data); display_recur(p->link); -38-
단순연결리스트의탐색연산 탐색연산 ~ 특정한데이터값을갖는노드를찾는연산 ListNode *search(listnode *head, int x) { ListNode *p; p = head; while( p!= NULL ){ if( p->data == x ) return p; // 성공 p = p->link; return p; // 탐색실패일경우 NULL 반환 head NULL NULL NULL p -39-
단순연결리스트의합병연산 합병연산 ~ 2 개의리스트를합하는연산 head1 NULL NULL NULL head2 NULL NULL NULL -40-
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; -41-
단순연결리스트구현 ( in Java) 단순연결리스트 (Simple Linked-List) ~ 연결리스트의가장단순한형태 ~ 각노드들은오직하나의링크를갖기때문에하나의노드만을가리킨다. -> 단방향성 ~ 마지막노드의링크 null 값을가리킬경우는리스트의끝을나타냄. ~ 헤더 null 값을가리킬경우는빈리스트를나타냄 값을갖지않는다. -42-
4.1 노드구조 class LinkNode { private int idata; // 자료 ( 키 ) private LinkNode nodenext; // 다음노드포인터 // 생성자 public LinkNode( int idatainput ) { idata = idatainput; idata nodenext LinkNode -43-
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; -44-
4.2 insertfirst() 메소드 insertfirst() ~ 새로운노드를리스트의가장첫번째자리에삽입하는메소드 a) 2 를삽입하기전의리스트 b) 2 를삽입한후의리스트 -45-
public void insertfirst( int ikey ) { // 새로운노드생성 LinkNode nodenew = new LinkNode(iKey); // 새로운노드는기존의첫번째노드를참조 nodenew.setnodenext( HeaderNode.getNodeFirst() ) ; // 헤더는새로운노드를참조 HeaderNode.setNodeFirst( nodenew ); -46-
4.3 deletefirst() 메소드 deletefirst() ~ 리스트의첫번째노드를삭제하는역할을수행 a) 3 을삭제하기전의리스트 b) 3 을삭제한후의리스트 -47-
public LinkNode deletefirst() { // 빈리스트인지확인 if (HeaderNode.isEmpty() == false) { LinkNode tempnode = HeaderNode.getNodeFirst(); // 헤더는두번째노드를참조 HeaderNode.setNodeFirst ( HeaderNode.getNodeFirst().getNodeNext() ); return tempnode; // 삭제된노드를반환 else return null; // 빈리스트라면 null값반환 -48-
findnode() 4.4 findnode() 메소드 ~ 리스트내에서특정자료를갖고있는노드를찾는메소드 public LinkNode findnode( int ikey ) { // 리스트의첫번째노드부터탐색 LinkNode current = HeaderNode.getNodeFirst(); // 키값을탐색 while (current.getdata()!= ikey) { current = current.getnodenext(); // 다음노드검색. return current; // 키값갖고있는노드를반환 -49-
4.5 displaylist() 메소드 displaylist() 메소드 ~ 리스트로연결되어있는모든자료들즉, 각노드에저장되어있는자료들을출력하는메소드 public void displaylist() { // 리스트의첫번째노드부터출력 LinkNode current = HeaderNode.getNodeFirst(); while (current!= null) { current.displaynode(); // 노드자료출력 System.out.println(""); current = current.getnodenext(); // 다음노드탐색 -50-
4.6 insertnode() 메소드 insertnode() ~ 리스트에새로운노드를특정위치에삽입하는메소드 a) 8 을삽입하기전의리스트 b) 8 을삽입한후의리스트 -51-
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 ); -52-
4.7 deletenode() 메소드 deletenode() ~ 리스트에서특정노드를검색한후삭제하는메소드 a) 8 을삭제하기전의리스트 b) 8 을삭제한후의리스트 -53-
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; -54-
개념 5. 이중말단연결리스트 (Double-Ended Linked-List) ~ 단순연결리스트와유사한구조 ~ 헤더가첫번째노드뿐만아니라마지막노드를가리키는포인터를함께갖고있음 -55-
5.2 감시노드 class LinkSentinelNode { private LinkNode nodefirst; private LinkNode nodelast; // 첫번째노드를참조 // 마지막노드를참조 // 생성자 public LinkSentinelNode() { nodefirst = null; nodelast = null; // 첫번째노드를참조하는포인터접근메소드 public LinkNode getnodefirst() { return nodefirst; -56-
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); -57-
5.3 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 ); -58-
// 새로운노드를첫번째자리로삽입 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 ); -59-
5.4 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() ); -60-
else if (HeaderNode.getNodeLast() == current) { previous.setnodenext( null ); HeaderNode.setNodeLast( previous ); // 중간노드를삭제할경우 else { previous.setnodenext( current.getnodenext()); // 삭제된노드를반환 return current; -61-
5.5 displaylastnode() public void displaylastnode() { HeaderNode.getNodeLast().displayNode(); System.out.println(""); -62-
6. 이중연결리스트 (doubly linked list) 개념 ~ 하나의노드가선행노드와후속노드에대한두개의링크를가지는리스트 ~ 링크가양방향이므로양방향으로검색이가능 ~ 공간을많이차지하고코드가복잡 ~ 실제사용되는이중연결리스트의형태 헤드노드 + 이중연결리스트 + 원형연결리스트 헤드노드 -63-
헤드노드 (head node) ~ 데이터를가지지않고단지삽입, 삭제코드를간단하게할목적으로만들어진노드 ~ 헤드포인터와의구별필요 ~ 공백상태에서는헤드노드만존재 이중연결리스트의노드구조 typedef struct DlistNode { int data; struct DlistNode *llink; struct DlistNode *rlink; DlistNode; llink data rlink -64-
삽입연산 before (4) (1) (2) (3) new_node -65-
// 노드 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) -66-
삭제연산 (1) (2) removed -67-
// 노드 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); -68-
p = p->llink->rlink = p->rlink->llink 200 300 llink rlink llink rlink llink rlink 100 200 100 번지 200 번지 300 번지 p -69-
이중연결리스트구현 ( in Java) class LinkNode { private int idata; // 자료 ( 키 ) private LinkNode nodenext; // 다음노드참조포인터 private LinkNode nodeprevious; // 이전노드참조포인터 public LinkNode( int idatainput ) { // 생성자 idata = idatainput; public void displaynode() { // 노드자료출력메소드 System.out.print( idata ); public int getdata() { // 데이터접근메소드 return idata; -70-
public void setdata( int inputdata ) { // 자료변경메소드 idata = inputdata; public LinkNode getnodenext() { // 다음노드참조자접근메소드 return nodenext; public void setnodenext( LinkNode inputnode ) {// 다음노드참조자를변경하는메소드 nodenext = inputnode; public LinkNode getnodeprevious(){ // 이전노드참조자접근메소드 return nodeprevious; public void setnodeprevious( LinkNode inputnode ) {// 이전노드참조자를변경하는메소드 nodeprevious = inputnode; -71-
6.2 이중연결리스트 insertfirst() insertnode() 메소드 ~ 일반노드추가시 nodeprevious 참조자를위한과정이추가 ~ nodenext와 nodeprevious가다음노드와이전노드를참조하는참조자의역할 -72-
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(); -73-
// 빈리스트일경우 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 ); -74-
// 새로운노드를마지막자리로삽입 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 ); -75-
6.3 이중연결리스트 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(); -76-
// 첫번째노드를삭제할경우 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; -77-
7. 원형연결리스트 원형연결리스트 (Circular linked list) ~ 마지막노드의링크가첫번째노드를가리키는리스트 ~ 한노드에서다른모든노드로의접근이가능 head NULL NULL ~ 보통헤드포인터가마지막노드를가리키게끔구성하면리스트의처음이나마지막에노드를삽입하는연산이단순연결리스트에비하여용이 NULL NULL head -78-
원형연결리스트의처음에삽입 (2) A B NULL C NULL D (1) E head node -79-
// 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; -80-
원형연결리스트의끝에삽입 (2) A B NULL C NULL D (1) (3) E head node -81-
// 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; -82-