[Fundamentals of Data Structures in c++] 링크드리스트 오름차순 Insert함수 구현

Linked List 오름차순 Insert함수 구현

1. Insert 함수란?

• 정렬되어 있는 리스트에서 새로운 노드를 순서에 맞게 삽입하는 기능을 수행.

2. Node의 정의

struct Node {
 Node(int d = 0, Node *l = 0) : data(d), link(l) {}
 int data;
 Node *link;
};

3. Insert 함수의 구현

• 리스트가 비어있을 경우 노드가 first와 last 역할을 함.
• 이미 리스트에 같은 값이 존재할 경우 ->  건너 뜀
• p->link = null 일 때까지 일치하는 값이 없을 경우, 이 노드는 가장 큰 노드이므로 맨 마지막에 삽입 되어야 함.
• 노드가 제자리를 찾았을 경우, 그 위치에 삽입
• 리스트는 이미 오름차순으로 정렬 되어 있음. 따라서 어느 하나라도 노드의 데이터보다 큰 값을 가지는게 있다면 노드는 제일 작은 수 이므로 first로 연결해 주어야 함.

4. Insert 함수 소스 코드

void IntList::Insert(int e) {

 if (!first) {
  first = last = new Node(e);
 }
 else {
  for (Node *p = first; p != 0; p = p->link) {
   if (p->data == e) {
    break;
   }
   else if (p->link == 0) {
    last->link = new Node(e);
    last = last->link;
    break;
   }
   else if (p->data < e && p->link->data > e) {
    Node *node = new Node(e);
    node->link = p->link;
    p->link = node;
    break;
   }
   else if (e < p->data) {
    Node *node = new Node(e);
    node->link = first;
    first = node;
    break;
   }

  }

 }

}

5. 프로그램 결과

기존의 정렬된 리스트 : 3 4 5 7 9
리스트에 6, 10, 2, 5, 2, 10 을 insert 수행