[C] 연결리스트

서론

연결리스트를 C언어로 구현하고자 한다

왜냐면 자료구조 수업을 듣고있기 때문이다...

본론

구조체 정의

// 단순 연결리스트의 노드 구조 정의
typedef struct ListNode {
    int data;
    struct ListNode* link; 
} listNode;

// 리스트의 헤드 노드 구조 정의
typedef struct {
  listNode* head;
} linkedList_h;

 

연결리스트 생성

linkedList_h* createLinkedList_h(void) {
  linkedList_h* H;
  H = (linkedList_h*)malloc(sizeof(linkedList_h));
  H -> head = NULL;
  return H;
}

 

노드 삽입

void addNode(linkedList_h* H, int x) {
  listNode* NewNode;
  listNode* LastNode;

  NewNode = (listNode*)malloc(sizeof(listNode));
  NewNode -> data = x;
  NewNode -> link = NULL;

  // 연결되어 있지 않은 경우
  if (H -> head == NULL) {
    H -> head = NewNode;
    return;
  }

  // 리스트의 첫번째 노드부터 시작
  LastNode = H -> head;

  // 마지막으로 연결되어있는 노드를 찾음
  while(LastNode -> link != NULL) {
    LastNode = LastNode -> link;
  }
  // 삽입된 노드를 연결리스트 마지막에 추가
  LastNode -> link = NewNode;
}

 

중간에 노드 삽입

void addItNode(linkedList_h* H, listNode* prevNode, int itData) {
  listNode* NewNode;
  NewNode = (listNode*)malloc(sizeof(listNode));
  NewNode -> data = itData;
  NewNode -> link = NULL;

  NewNode -> link = prevNode -> link;
  prevNode -> link = NewNode;
  return;
}

 

노드 삭제

void deleteNode(linkedList_h* H) {
  listNode* prevNode;
  listNode* delNode;

  // 공백 리스트인 경우
  if (H -> head == NULL) return;

  // 리스트 노드가 한 개인 경우
  if (H -> head -> link == NULL) {
    free(H -> head);
    H -> head = NULL;
    return;
  }

  // 리스트에 노드가 여러 개 있는 경우
  prevNode = H -> head;
  delNode = H -> head -> link;
  while(delNode -> link != NULL) {
    prevNode = delNode;
    delNode = delNode -> link;
  }

  free(delNode);
  prevNode -> link = NULL;
}

 

중간 노드 삭제

void deleteItNode(linkedList_h* H, listNode* prevNode, listNode* delNode) {
  prevNode -> link = delNode -> link;
  free(delNode);
  return;
}

 

특정 노드 삭제

void findAndDeleteNode(linkedList_h* H, int itData) {
  listNode* prevNode;
  listNode* delNode;

  // 공백 리스트
  if (H -> head == NULL) return;

  prevNode = H -> head;
  delNode = H -> head;

  while (delNode != NULL) {
    if (delNode -> data == itData) {
      deleteItNode(H, prevNode, delNode);
      return;
    }

    prevNode = delNode;
    delNode = delNode -> link;
  }
}

 

결론

c언어에 좀 더 익숙해져야겠다