[자료구조] 연결리스트의 종류와 특성

 

연결리스트의 종류

- 단순 연결 리스트(singly Linked List)

자료들이 링크로 서로 연결되어 있는 형태

 

 

- 원형 연결 리스트(Circular Linked List)

가장 마지막 자료가 가장 처음 자료와 연결되어 있는 형태

- 이중 연결 리스트(Double Linked List)

 

앞뒤자료가 서로서로에게 양쪽으로 연결되어 있는 형태

 

연결리스트의 특성 비교

- 이전 노드에 대한 접근 연산

단순 연결 리스트	이전노드를 접근할수 있는 방법이 없음 무조건 가장 처음 노드부터 검색해야함
원형 연결 리스트	계속 가다보면 나의 이전 노드의 값을 찾을 수 있다
이중 연결 리스트	이중으로 연결되어 있기 때문에 바로 이전 노드를 접근 할 수 있다

 

단순 연결 리스트

LinkedList 구조체

헤더 노드의 사용목적 : 구현의 간편함

#ifndef _LINKEDLIST_
#define _LINKEDLIST_

typedef struct ListNodeType{
  int data;
  struct ListNodeType* pLink;
} ListNode;

typedef struct LinkedNodeType {
  int currentElementCount;		//현재 저장된 원소의 개수
  ListNode headerNode;         // 헤더 노드
} LinkedList;

 

 

노드 추가

 

이전노드에서 현재 추가하려는 노드를 제거하고 새로 추가되려는 노드를 연결해준다

 

int addLLElemewnt(LinkedList* pList, int position, ListNode element){
  int ret = FALSE;
  int i = 0;
  ListNode* pPreNode = NULL;
  ListNode* pNewNode = NULL;
  if(pList != NULL){
    if(position >= 0 && position <= pList->currentElementCount) {
      pNewNode = (ListNode*)malloc(sizeof(ListNode));
      if(pNewNode != NULL) {
        *pNewNode = element ;
        pNewNode -> pLink = NULL;
        
        pPreNode = &(pList -> headerNode);
        for(i =0; i< position; i++){
          pPreNode = pPreNode -> pLink;
        }
        
        pNewNode -> pLink = pPreNode -> pLink;
        pPreNode -> pLink = pNewNode;
        
        pList -> currentElementCount++;
        ret = TRUE;
      }else{
        printf("오류, 메모리 할당 addLLElement()\n");
        return ret; 
      }
    }
    else {
    printf("오류, 위치 인덱스 - [%d], addLLElement()\n",position);
   }
 }    

노드 제거

이전노드와의 연결 제거 후 제거하려는 노드의 다음 노드와 연결시킨다

int removeLLElement (LinkedList* pList, int position) {
  int ret = FALSE;
  int i = 0;
  int nodeCount =0;
  ListNode* pPreNode = NULL;
  ListNode* pDelNode = NULL;
  if(pList != NULL){
     nodeCount = getLinkedListLength(pList);
     if(position >=0 && position < nodeCount){
       pPreNode = &(pList -> headerNode);
       for(i = 0; i < position ; i++){
         pPreNode  = pPreNode -> pLink;
       }
       
       pDelNode = pPreNode -> pLink;
       pPreNode -> pLink = pDelNode ->pLink;
       free(pDelNode);
       
       pList ->currentElementCount--;
       ret = TRUE;
     }
     else {
       printf("오류, 위치인덱스 - [%d] removeLLElement()\n",position);
    }
  }
  
  return ret;
}

원형 연결 리스트

리스트의 마지막 노드가 가장 첫번째 노드와 연결되어 순환되는 구조

헤드 포인터를 이용하여 구성되어 있다

 

노드 추가

포인터를 이용하기때문에 3가지 경우를 생각해야한다

 

case 1-1

자기자신을 가리키도록 한다

case 1-2

새로 추가되는 노드를 바라보도록 함

case 2

단순 연결리스트와 비슷하다고 볼 수 있다

노드제거

 case 1-1

리스트 마지막 남은 노드를 제거

헤더 포인터가 널이 된다

case 1-2

헤더 포인트가 제거하려는 노드의 다음노드를 가리키도록 설정, 마지막 노드가 제거된 이후의 노드를 바라봄

case 2

이중연결리스트

노드들이 양방향으로 서로 연결 되어 있는 형태로 양 방향에 링크가 존재한다

장점 : 이전노드가 바로 접근가능

단점 : 링크에 대한 추가 메모리가 필요하다

 

헤더 노드를 이용하여 진행한다

pNode == pNode -> pLLink ->pRLink == pNode ->pRLink -> pLLink

위 조건이 항상 만족한다

 

노드 추가

링크 두개를 삭제하고 연결한다

pNewNode -> pLLink = pPreNode;
pNewNode -> pRLink = pPreNode -> pRLink;
pPreNode -> pRLink = pPreNode;
pNewNode -> pRLink = pLLink -> pNewNode;

노드제거

삭제하는 노드의 연결된 링크를 끊고 해당 노드의 다음 노드로 연결시킨다

pDelNode =  pPreNode -> pRLink;
pPreNode -> pRLink = pDelNode -> pRLink;
 pDelNode -> pRLink -> pRLink = pPreNode;