4. Linked List

Linked List

Singled Linked List

각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다.

 

Example) 단어 정렬

단어들이 임의의 순서로 주어졌을 때 단일 연결 리스트를 사용하여 알파벳 순으로 단어를 배열하고 싶습니다. 단어 목록은 다음과 같습니다.

HAT, CAT, EAT, WAT, BAT, FAT, VAT

알파벳순 정렬을 할 때 Link의 숫자는 다음 data의 숫자입니다.

data[4] = bat;
link[4] = 1;

data[link[4]] = data[1] = cat;
link[1] = 2;

...

위와 같이 단일 연결 리스트란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다.

 

 

• 추가

새노드 gat를 연결 리스트에 삽입해보자.

 

 

• 삭제 

노드 gat을 삭제해보자

 

연결리스트 API

• 개별 노드 생성

typedef struct node *pNode;
// 자기참조 구조체 포인터변수
typedef struct node {
    int data;
    pNode next;
};

pNode newNode (pNode next, int item) {
    pNode aNode = (pNode)malloc(sizeof(node));
    assert (aNode != NULL);
    
    aNode->item = item;
    aNode->next = next;
    
    return aNode;
}

 

• 리스트 생성 (헤드노드, 빈 리스트)

typedef struct list *pList;
typedef struct list {
    pNode head;
    pNode tail;
    int size;
};

pList newList() {
    pList newList = (pList)malloc(sizeof(list));
    assert(newList != NULL);
    
    newList->head = NULL;
    newList->tail = NULL;
    newList->size = 0;
    return newList;
}

 

• 삽입
  • 첫 부분에 삽입

  void insertFront(pList p, int item) {
      p->head = newNodeX(p->head, item);
      p->size++;
  
  	if (p->size == 1)
  		p->tail = p->head;	// only one node
  
  }
  

  
  
  • 중간부분에 삽입

  // inserts a node at an index, 0 for front
  void insertIndex(pList p, int item, int index) {
  	if (index < 0)
  		return;
  
      pNode curr = p->head;
      int nodeCount = size(p);
      
      if (index == 0) insertFront(p, item);
      
      else {
          for (int i = 1; i < index; i++) {
              curr = curr->next;
          }
  
          curr->next = newNodeX(curr->next, item);
      }
  	p->size++;
  }
  

  
  
  • 끝 부분에 삽입

  void insertLast(pList p, int item) {
      
      pNode head = p->head;
      while (head->next != NULL) {
          head = head->next;
      }
  
      head->next = newNode(item);
      p->size++;
  }
  

  
  
  • 정렬해서 삽입

  void insertSorted(pList p, int item) {
      // there is no item or item is smaller than first item
      pNode curr = p->head;
      pNode aNode = curr->next;
  
  	if (curr == NULL || item < curr->item)
  		insertFront(p, item);
          
      else {
          while (aNode != NULL) {
              if (item > curr->item && item <= aNode->item) {
                  curr->next = newNodeX(aNode, item);
                  p->size++;
                  break;
              }
  
              curr = curr->next;
              aNode = aNode->next;
          }
      }
  }
  

•  삭제
  • 시작 노드 삭제

  void deleteFront(pList p) {
      pNode curr = p->head;
      pNode aNode = curr->next;
  
      free(curr);
  
      p->head = aNode;
    p->size--;
  
    while (aNode != NULL) {
          aNode = aNode->next;
    }
  
    if (p->size == 0) p->tail = NULL;
  }
  

  
  
  • 중간 노드 삭제
    • case1: 지우고 싶은 노드와 그 앞 노드를 알때

    void deleteMiddleWithTrail (pNode trail, pNode x) {
        trail->next = x->next;
      free(x);
    }
    

    
    • case2: 지우고 싶은 노드와 리스트만 주어질 때

    void deleteNode(pList p, int item) {
      pNode curr = p->head;
        pNode aNode = curr->next;
  
        if (curr->item == item) {
  		deleteFront(p);
            return;
    	}
    
      while (aNode != NULL) {
            if (aNode->item == item) {
                curr->next = aNode->next;
                free(aNode);
                p->size--;
                break;
            }
            curr = curr->next;
            aNode = aNode->next;
        }
    }
  

  
  • 마지막 노드 삭제

  // Time Complexity: O(n)
  void deleteLast(pList p) {
      pNode curr = p->head;
      pNode aNode = curr->next;
  
  	p->size--;
  	if (p->size == 0)
  		p->head = NULL;
  
      if (isEmptyList(p)) {
          return;
      }
  
      else {
          while (aNode->next != NULL) {
              printf("curr: %d  aNode: %d\n", curr->item, aNode->item);
              curr = curr->next;
              aNode = aNode->next;
          }
  
          curr->next = aNode->next;
          free(aNode);
      }
  }
  

 

•  검색
  • int search(pList p, int item)

  /** returns index of item if found, -1 if not */
  int search(pList p, int item) {
      pNode head = (pNode)malloc(sizeof(pNode));
      head = p->head;
      int index = 0;
  
      while (head != NULL) {
          if (head->item == item) {
              return index;
          }
  
          head = head->next;
          index++;
      }
  
      return -1;
  }
  

  
  
  • void traverse(pList p)

  void traverse(pList p) {
  
  	if (isEmptyList(p)) {
  		printf("\n\tThe list is empty.\n");
  		return;
  	}
  
      pNode head = p->head;
      
      printf("\n\t[0..%d]: [%d", size(p)-1, head->item);
      head = head->next;
  
      while (head != NULL) {
          printf(" -> %d", head->item);
          head = head->next;
      }
  	printf("]\n");
  }
  

 

• internal use
  • void freeNode(pNode p)

  void freeNode(pNode headNode) {
      if (headNode->next == NULL) free(headNode);
      else {
          pNode temp = (pNode)malloc(sizeof(pNode));
          while (headNode != NULL) {
              temp = headNode;
              headNode = headNode->next;
              free(temp);
          }
      }
  }
  

  
  
  • void freeList(pList p)

  void freeList(pList p) {
      if (!isEmptyList) {
          free(p->head);
          free(p);
      }
  }
  

  
  
  • bool isEmpty(pList p)

  bool isEmptyList(pList p) {
  	return p == NULL || p->head == NULL;
  }
  

  
  
  • int size(pList p)

  int size(pList p) {
  	return p->size;
  }
  

  
  
  • int getSize(pList p)

  // internal use - count nodes in list
  int getSize(pList p) {
  	if (isEmptyList(p)) return 0;
  	int count = 0;
  	for (pNode x = p->head; x != NULL; x = x->next) 
          count++;
  	return count;
  }
  

 

Doubled Linked List

 

Circular Linked List