리스트

자료를 순서대로 저장하는 자료구조

• 리스트 생성: 최대 원소 개수 n
• 원소 추가: 원소 추가 가능 여부 판단
• 원소 반환
• 원소 제거: 리스트 초기화
• 리스트 삭제

---

배열 리스트 (Array List)

논리적 순서와 물리적 순서가 동일한 리스트

• 원소의 위치 인덱스는 0부터 시작

원소의 개수가 10만 개인 배열 리스트에서 위치 0의 자료 제거 혹은 추가가 빈번하게 발생한다면?
⇒ 매 연산마다 모든 원소의 이동이 필요하므로 매우 느리고 비효율적

구현

🔗 전체 코드

구조체와 함수 원형

typedef struct ArrayListNodeType
{
	int	data;
} ArrayListNode;

typedef struct ArrayListType
{
	int				maxElementCount;		// 최대 원소 개수
	int				currentElementCount;	// 현재 원소의 개수
	ArrayListNode*	pElement;				// 원소 저장을 위한 1차원 배열
} ArrayList;

ArrayList*		createArrayList(int maxElementCount);	// arraylist 할당 및 생성
void			deleteArrayList(ArrayList** pList);		// arraylist free
int				isArrayListFull(ArrayList* pList);		// arraylist가 가득 찼는지 확인

int				addALElement(ArrayList* pList, int position, ArrayListNode element);	// arraylist node 추가
int				removeALElement(ArrayList* pList, int position);	// arraylist node 제거
ArrayListNode*	getALElement(ArrayList* pList, int position);		// arraylist node 가져오기

void			displayArrayList(ArrayList* pList);		// arraylist 출력
void			clearArrayList(ArrayList* pList);		// arraylist 초기화
int				getArrayListLength(ArrayList* pList);	// arraylist에 들어가있는 element의 길이 확인

---

연결 리스트 (Linked List)

논리적 순서와 물리적 순서가 동일하지 않은 리스트

• 앞 노드가 다음 노드의 주소를 가짐
• 자료 제거 혹은 추가 시 앞 노드의 링크만 수정하면 됨

노드

자료(data)와 링크(link)를 가지는 구조체

구현

🔗 전체 코드

구조체와 함수 원형

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

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

LinkedList	*createLinkedList();										 		// linkedlist 생성
int			addLLElement(LinkedList *pList, int position, ListNode element);	// 노드 추가
int			removeLLElement(LinkedList *pList, int position);					// 노드 제거
ListNode	*getLLElement(LinkedList *pList, int position);						 // 노드 가져오기

void		displayLinkedList(LinkedList *lst);		// linkedlist 출력
void		clearLinkedList(LinkedList *pList);		// linkedlist 초기화
int			getLinkedListLength(LinkedList *pList);	// linkedlist 노드의 개수 확인
void		deleteLinkedList(LinkedList **pList);	// linkedlist free

---

배열 리스트 vs 연결 리스트

	배열 리스트	연결 리스트
장점	인덱스로 한번에 원소에 접근할 수 있으므로 데이터 참조가 쉬움	최대 크기가 유동적 중간에 자료 추가 혹은 제거가 자유로움
단점	최대 크기가 고정적 중간에 자료 추가 혹은 제거가 번거로움 최대 크기가 너무 크면 메모리 할당이 힘듦	구현의 어려움 탐색 연산의 비용이 높음 (원소 개수가 n개: O(n)) 데이터 외에 링크를 저장하는 공간이 추가되어 메모리가 큼

데이터의 추가 및 삭제 연산이 잦고, 최대 크기가 유동적인 경우 연결 리스트를 사용
저장할 자료의 크기가 작고, 데이터의 참조가 잦은 경우 배열 리스트를 사용