[자료구조] 연결리스트 head에 추가, tail에 추가, dummy node 활용

'윤성우의 열혈 자료구조'의 Ch4. 연결리스트를 공부하면서 정리한 내용이다.

 

연결리스트에서 노드를 추가할 때, 뒤에 추가하는 방법과, 앞에 추가하는 방법이 있다.

두 코드에서 핵심적인 부분들만 가져왔다.

 

아래의 코드에서 사용하는 구조체는 이렇게 생겼다.

tail 에서 추가되는 연결리스트

 

head에서 추가되는 연결리스트

• tail에서 추가되는 방법은 tail 포인터가 움직이고,
  head에서 추가되는 방법은 head 포인터가 움직인다는 점이 다르다.

 

• 두 방법의 장단점 비교

	tail	head
장점	저장된 순서가 유지된다.	포인터변수 tail이 불필요하다.
단점	포인터변수 tail이 필요하다.	저장된 순서를 유지하지 않는다.

 

 

Dummy Node 활용

위에서 본 방법은, 노드를 추가, 삭제, 조회 하는 방법에 있어서 첫번째 노드와 나머지 노드가 다르다. 
더미 노드라는 빈 노드를 제일 앞에 넣어두면, 모든 노드에 대해 일관된 방법으로 추가, 삭제, 조회가 가능하다.

 

tail에서 추가되는 케이스

  Node *head = NULL;
  Node *tail = NULL;
  Node *cur = NULL;

  Node *newNode = NULL;
  int readData;

  head = (Node *)malloc(sizeof(Node));    // 더미 노드 추가
  tail = head;	

  while(1)
  {
      printf("자연수 입력: ");
      scanf("%d", &readData);
      if(readData < 1)
      	  break;

      /*** 노드의 추가과정 ***/
      newNode = (Node *)malloc(sizeof(Node));
      newNode->data = readData;
      newNode->next = NULL;

      tail->next = newNode;

      tail = newNode;
  }

head에서 추가되는 케이스

  Node *head = NULL;
  Node *tail = NULL;
  Node *cur = NULL;

  Node *newNode = NULL;
  int readData;

  // Dummy 노드 추가
  head = (Node *)malloc(sizeof(Node));
  tail = head;
  tail->next = NULL;

  /**** 데이터 추가 ****/
  while (1)
  {
      printf("자연수 입력: ");
      scanf("%d", &readData);
      if (readData < 1)
      break;

      /*** 노드의 추가 과정 ***/
      newNode = (Node *)malloc(sizeof(Node));
      newNode->data = readData;

      newNode->next = head;
      head = newNode;
  }