연결 리스트

 자료구조에는 여러 형식으로 데이터를 저장한다. 그리고 데이터를 저장하는 방식에 따라 선형형식, 비선형형식으로 나뉜다.

• 선형 구조 : 데이터를 1:1 관계로 하나씩 나열시킨 구조로, list, stack, queue가 해당 구조에 해당한다.
• 비선형 구조 :  데이터를 1:n 관계로 나열 시킨 구조로, Heap, Tree가 해당 구조에 해당한다.

 이중에서, 제일 많이 사용하는 자료구조가 "List"인데, "List"란 직선상으로 연결되어있는 노드에 데이터를 저장하는 자료구조이다.

 "List"에는 배열리스트와 연결리스트로 나뉜다. 배열 리스트는 배열의 형태로 노드를 연결해서 데이터를 저장하는 형식이며, 연결 리스트란 주소를 이용해서 노드를 연결하는 형식이다.

 

 이때, node(노드)란 데이터를 저장하는 공간으로, 구조체를 통해 해당 노드에 어떠한 데이터를 저장할지 결정한다. 

typedef struct LinkedListNodeType {
	int data;
    	LinkedListNode* pLink;
} LinkedListNode;

 위의 구조는 노드의 타입을 나타내는 구조로, 모든 사용자가 알 수 있도록 구조체의 이름을 공용화한 형태이다.

 

연결리스트

 연결 리스트란 주소를 이용해서 노드를 연결하는 자료구조로, 노드 생성 구조체에 자기 참조 구조체를 이용해서 다음 노드를 링크한다.

 위의 그림을 보면, 데이터를 저장하는 공간을 가지지 않고 다음 노드의 주소만 저장할 수 있는 노드가 있는데, 이를 헤더노드라고 한다. 헤더노드는 연결 리스트의 시작점으로, 실제 자료를 저장하는 노드가 아니기에 헤더노드는 노드번호/개수에 포함이 되지 않는다.

typedef struct LinkedListType {
	int currentCount;			//현재 사용중인 노드 갯수
	LinkedListNode* HeadNode;		//해더노드
}LinkedList;

 위의 구조는 연결 리스트의 정보를 나타내는 구조체로, 구조체를 통해 연결 리스트의 정보와 노드의 시작점을 확인 할 수 있다.

 

연결 리스트의 알고리즘

 연결 리스트 데이터를 저장할 수 있는 노드가 주소로 연결되어있는 형태이기에, 노드를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 기능의 순서도를 구성하고, 소스코드로 구현해야 한다.

 

• 연결 리스트 헤더노드 생성 함수
  • 기능 : 노드를 연결할 헤더노드 생성하며, 해당 리스트의 정보(연결중인 노드의 갯수) 저장
  • 함수의 자료형: ArrayList의 포인터(ArrayList*)
  • 필드 사용 변수
    
    • pList ←  연결리스트 정보 변수

알고리즘

리스트 정보 변수를 동적 메모리로 생성 후, 변수의 주소를 포인터 변수에 저장 리스트 정보 초기화 리턴 값을 리스트 정보를 가진 변수의 주소를 가진 포인터 변수로 지정

LinkedList* createLinkedList() {
	LinkedList* pReturn = (LinkedList*)malloc(sizeof(LinkedList));
	memset(pReturn, 0, sizeof(LinkedList));
	return pReturn;
}

 

• 연결리스트 노드 삽입
  • 기능
    • 연결 리스트의 헤더 노드에 연결
      1. 헤더노드에 저장되어 있는 주소 새 노드의 주소 칸에 저장
      2. 새 노드의 주소를 헤더노드에 저장
    • 연결 리스트의 마지막 노드에 연결 : 마지막 노드의 포인터 변수에 삽입할 노드의 주소 저장
    • 연결리스트의 중간 노드에 연결 
      1. 삽입하는 장소의 전 노드의 주소를 삽입할 노드의 포인터 변수에 저장
      2. 삽입할 노드의 주소를 삽입하는 장소의 전 노드의 포인터 변수에게 저장
  • 함수의 자료형 : void
  • 매개변수 : 노드를 추가할 리스트(pList), 들어갈 노드 위치(point), 노드에 저장할 내용(data)
  • 필드에서 사용할 변수
    • 새로운 노드 주소 ← newNode
    • 삽입하는 장소의 전 노드 주소 ← preNode

알고리즘

새로운 노드 생성후 데이터 저장 시작위치 헤더노드로 설정 반복문을 통해, preNode를 삽입 이전 노드로 설정 newNode의 주소칸 에 preNode의 주소칸에 있는 주소 저장 preNode의 주소칸에 newNode의 주소 저장

void insertNode(LinkedList* pList, int point, int data) {
	LinkedListNode* newNode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
	newNode->data = data;

	LinkedListNode* preNode = &(pList->HeadNode); //시작 위치 : 헤더노드

		for (int i = 0; i < point; i++) {
			preNode = preNode->pLink;
		}
		newNode->pLink = preNode->pLink;
		preNode->pLink = newNode;
		pList->currentCount++;
		printf("현재 사용중인 노드의 수 : %d\n", pList->currentCount);
	
}

 

• 연결리스트 노드 삭제
  • 기능 : 지정한 연결리스트의 노드를 제거
  • 함수의 자료형 : void
  • 매개변수 : 노드를 삭제할 리스트(pList), 삭제할 노드 위치(point)
  • 필드에서 사용할 변수
    
    • 삭제하는 장소의 전 노드 주소 ← preNode
    • 삭제할 노드 ← delNode

알고리즘

preNode를 헤더노드로 설정 반복문을 통해 지정한 노드의 전 노드로 설정 delNode를 preNode의 다음노드로 설정 delNode의 주소 칸에 있는 주소를 preNode의 주소칸에 저장 delNode의 메모리 할당 해제

void delLinkedListNode(LinkedList* pList, int point) {
		int i = 0;
		LinkedListNode* delNode = NULL;
		LinkedListNode* preNode = NULL;

		preNode = &(pList->HeadNode);
		for (i = 0; i < point; i++) {
			preNode = preNode->pLink;
		}

		delNode = preNode->pLink;
		preNode->pLink = delNode->pLink;
		free(delNode);
		pList->currentCount--;
		return 0;
	
}

 

• 연결리스트 제거
  • 기능 : 지정한 연결리스트 삭제
  • 매개변수 :  삭제할 연결리스트(pList)
  • 필드 사용 변수
    1. 연결리스트의 가장 앞에 있는 노드 ← frontNode
    2. frontNode를 삭제하고 다음에 삭제할 노드 ← nextNode

void deleteLinkedList(LinkedList* pList) {
	LinkedListNode* frontNode = NULL;
	LinkedListNode* nextNode = pList->headerNode.pLink;
	while (nextNode != NULL) {
		frontNode = nextNode;
		nextNode = nextNode->pLink;

		free(frontNode);
	}

	free(pList);
}