자료구조 리스트(List) 기초 개념정리

추상자료형(Abstract Data Type)

추상자료형 이란 간단히 ADT라고도 불리며, 프로그래밍을 공부하면 볼 수 있는 용어 입니다. ADT는 구체적인 기능의 완성과정을 언급하지 않고 단순히 기능이 무엇인지를 나열한 것 입니다.

---

리스트

리스트자료구조는 데이터를 나란히 저장하며, 중복된 데이터의 저장을 허용합니다.

순차리스트: 배열기반의 리스트, 메모리의 특성이 정적이다.

연결리스트: 메모리의 동적할당 기반의 리스트

배열기반리스트

배열기반리스트는 연결리스트에 비해서 참조가 쉽습니다. 또한 인덱스 값을 기준으로 사용하여 어느 위치든 한번에 참조가 가능합니다.

배열기반리스트의 단점으로는 삭제과정을 거칠때마다 데이터의 이동이 필요하기 때문에 효율이 떨어지며, 배열의 길이가 초기화할때 정해져야하며 변경이 불가능하다는 점 입니다.

연결리스트

연결리스트의 기본 원리는 필요할때마다 바구니 역활을 하는 구조체 변수(Node)를 하나씩 동적할당 한 후 연결하는 것이다. 

ex) Node1 -> Node2 -> Node3 -> NULL

기초적인 연결리스트 예제

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct _node {		//node 구조체 정의
	int data;
	struct _node* next;
}Node;

int main()
{
	Node* head = NULL;		//head 노드 선언
	Node* tail = NULL;		//tail 노드 선언
	Node * cur = NULL;		//cur 노드 선언, 저장된 데이터조회를 위한 변수

	Node* newNode = NULL;	//노드를 추가하기 위한 노드
	int readData;		//데이터를 저장하기 위한 변수

	while (1) {		//데이터를 입력하고 저장하는 while문
		printf("데이터입력: ");
		scanf("%d", &readData);

		if (readData < 1)		//데이터가 1보다작으면 반복문 종료
			break;

		newNode = (Node*)malloc(sizeof(Node));	//newNode 동적할당
		newNode->data = readData;		//scanf로 입력한 데이터를 newNode 데이터에 저장
		newNode->next = NULL;

		if (head == NULL)		//head가 비어있으면
			head = newNode;		//newNode 저장
		else
			tail->next = newNode;		//head가 비어있지않으면 tail의 다음노드로 newNode 저장

		tail = newNode;		//tail은 마지막 노드를 가리키게 된다.
	}
	printf("\n");

	printf("입력받은데이터출력:");
	
	if (head == NULL)
		printf("입력된데이터가 없습니다.\n");
	else
	{
		cur = head;		//cur에 head를 대입
		printf("%d ", cur->data);	//cur의 데이터 출력

		while (cur->next != NULL) {	//cur의 다음노드가 NULL일때까지 데이터출력
			cur = cur->next;
			printf("%d ", cur->data);
		}
	}
	printf("\n");

	if (head == NULL)		//데이터삭제를 위한 조건문 시작
		return 0;
	else {
		Node* delNode = head;		//데이터삭제를 위한 노드
		Node* delNextNode = head->next;		

		printf("%d를 삭제합니다.\n", head->data);
		free(delNode);

		while (delNextNode != NULL) {		//다음노드가 NULL일때까지 데이터를 삭제
			delNode = delNextNode;
			delNextNode = delNextNode->next;

			printf("%d를 삭제합니다.\n", delNode->data);
			free(delNode);
		}
	}
	return 0;
}

참고: 윤성우의 열혈자료구조