C언어 자료구조 연결리스트(4) LinkedList

o오늘 배울 것들
 1) 연결리스트의 index번째 노드의 주소를 반환한다.

 2)index번째 위치에 새로운노드를 만들어서 삽입한다.
 3)index번째 노드를 삭제하고, 그 노드에 저장된 데이터를 반환한다.
 4)입력된 스트링을 저장한 노드를 찾아 삭제한다. 

 5)연결리스트에 데이터들이 오름차순으로 정렬
 되어 있다는 가정하에 새로운 데이터를 삽입한다. 

1) 연결리스트의 index번째 노드의 주소를 반환한다.

Node *get_node(int index) {
if(index <0) 
return NULL; //해당 노드가 없다면 null을 리턴한다. 
Node *p = head;
for(int i=0; i<index && p!=NULL; i++) 
p = p->next; //인덱스칸만큼 전진한다. 
return p;
} 

 //index가 5까지 있다는 가정하에
 //네번째노드의 인덱스는 3이 된다.
 //만약 노드주소가 없다면 null을 리턴해준다
 //outOflength를 방지하기 위해서 NUll이 아닌만큼 반복한다 / p!=NULL


 2) index번째 위치에 새로운노드를 만들어서 삽입한다.

 /*
  함수 참고
 int add_after(Node *prev, char *item) 
{
if(prev ==NULL)
return 0;    //실패하면 0반 
Node *tmp = (Node *)malloc(sizeof(Node));
tmp->data = item;
tmp->next = prev->next;
prev->next = tmp;

return1; // 성공하면 1반환 

 } 

 */

 //index 번호에 따라서 몇번째에 노드를 삽입한다 
 int add(int index, char *item) {
  if(index <0) 
  return 0; //예외처리
 
Node *tmp = (Node *)malloc(sizeof(Node)); //새로운 노드생성 
tmp->data = item;                        //추가할 데이 
tmp->next = NULL;                        //일단 null을 넣는다. 

//노드 인덱스가 맨앞(0)인 경우와 그렇지 않은 경우 별개로 코딩한다. 
if(index == 0) {   
add_first(item); //새로운 노드생성 
return 1;
}

Node *prev = get_node(index-1);  //끼워놓을 노드의 이전인덱스라서 -1해준다. 
if(prev != NULL) {
add_after(prev, item);
return 1;
}
return 0;
 } 

 3)index번째 노드를 삭제하고, 그 노드에 저장된 데이터를 반환한다.

 !항상 명심해야 할것은 삭제할 노드의 왼쪽번째
 노드의 주소를  리턴하고 삭제해야한다.

 Node *remove(int index) {
  if(index <0) {
  return NULL;
}
  if(index ==0) {
  return remove_first();
}
  Node *prev = get_node(index-1);  //해당 노드의 왼쪽번째 
  if(prev==NULL)
  return NULL;
  else{
  return remove_after(prev);  //삭제한 노드의 주소를 받아서 리턴한다 
}
 }
  

4)입력된 스트링을 저장한 노드를 찾아 삭제한다.

Node *remove(char *item) {
Node *p = head;
while (p!= NULL && strcmp(p->data, item) != 0)
p= p->next;

??? //  여기서 문제점이 발생한다. 삭제할 노드를 가리키는 
    //왼쪽 노드의 주소를 찾아야 삭제할 수 있따.  
}




그래서

Node *remove(char *item) {
Node *p = head;
Node *q = NULL;
while (p!=NULL && strcmp(p->data, item) != 0)/*다른경우*/ {
q = p;   //p의 주소를 q에 넣어서.  
p = p->next; //q는 항상 p따라가게 된다
}
if(p==NULL)
return NULL;

if(q==NULL)  //첫번째 노드를 삭제할 경우. q는 while문을 빠져나오게 된다.  
return remove_first();
else
return remove_after(q);  
}

 /*p가 맨첫번째 노드라면 q는 head의 주소인 null을 가리키게 된다
 그래서 while문을 빠져나오게 된다  */



 5)연결리스트에 데이터들이 오름차순으로 정렬
 되어 있다는 가정하에 새로운 데이터를 삽입한다.



void add_to_ordered_list(char *item) {
Node *p = head;
Node *q = NULL;
while (p!=null && strcmp(p->data, item)<=0) {
q=p;
p=p->next;
}
if(q==NULL) //노드를 맨앞에 삽입하는경우 q는 head의 주소값null을 갖게된다. 
add_first(item);
else
add_after(q);  //q다음 삽입한다.  미리 만들어놓은 함수를 참고하길 바란다. 
}



 만약   A B  F  Z가 있는데 여기서 D를  알파벳순으로 정렬된 리스트에서
 B 와 F 사이 들어가야 할 경우 , 어떻게 찾아서 넣을 것인가.
그 답은 순서대로 비교해서 삽입할 데이터가 크거나 같은경우 한칸씩 전진한다.
만약 다음 이동할 노드보다 작다면 그 자리에 멈춘다

add_after은 있지만 add_before가 없는 경우를 생각해보자.
하지만 이럴 경우 문제가 생긴다.  어떤 노드를 삽입할때는  앞노드의 주소가 아니라
이전 노드의 주소가 필요하기때문에 q가 항상 p의 주소값을 가지고 p는 다음칸으로 전진한다는 이전 next의 주소를 갖게 된다, 즉 q가 p를 따라오게 만든다.
그러면 오류없이 노드를 추가 할 수 있다