추상 자료형(Abstract Data Type)
•
추상적으로 자료형을 정의
•
객체와 함수들이 존재
배열 리스트의 추상 자료형 예시
자료구조는 추상 자료형을 프로그래밍 언어로 구현한 것이라고 볼 수 있다!
리스트
항목들을 차례로 저장하는 방법 (버킷 리스트 등)
1) 배열 리스트
배열을 기반으로 구현된 리스트
2) 연결 리스트
노드의 동적 할당을 기반으로 구현된 리스트
노드(Node)
Show All
Search
연결 리스트의 종류
1) 단방향 연결 리스트
2) 원형 연결 리스트
3) 이중 연결 리스트
구현한 리스트 구조
// 단방향 연결 리스트 헤더 일부
typedef struct ListNodeType
{
int data;
struct ListNodeType* next;
} ListNode;
typedef struct LinkedListType
{
int currentElementCount;
ListNode *headerNode;
} LinkedList;
C
복사
•
LinkedList라는 구조체에 연결 리스트의 정보(현재 노드 개수, 헤더 노드 포인터)를 저장
•
헤더 노드(더미노드) : 리스트에서 실질적인 데이터를 가지는 첫번째 노드를 가리키도록 하는 노드
•
노드는 데이터 필드와 링크 필드로 나뉘는데 데이터 필드에 저장하고 싶은 데이터를 저장하고, 링크 필드에는 다른 노드를 가리키는 포인터가 저장된다
•
이중 연결 리스트는 2개의 링크 필드를 갖는다