메모리를 동적 할당하면서 데이터를 저장하는데, 다른 자료구조들의 구현에 바탕이 되는 경우가 많다. 가령 트리나 그래프도 연결 리스트에 기반해서 구현한다.
연결 리스트를 이해하기 위해서는 그림을 그려가며 이해하는 것이 좋다고 한다. 아래 그림은 https://www.interviewbit.com/courses/programming/topics/linked-lists/tutorial/introduction-to-linked-list/ 에서 퍼왔다.
여기를 보면 head, tail, 그리고 각각의 네모 상자들이 있는데 각 상자는 둘로 나뉘어져 하나는 값을, 하나는 다음 상자에 대한 화살표를 담고 있다. 이 각각의 네모들을 node 라고 한다. 각 node는 정보를 담는 상자인데 다음과 같이 구성된다.
1
2
3
4
5
|
typedef struct _node{
int data;
struct _node *next;
} Node;
| cs |
여기서 data는 담고자 하는 데이터로, int가 아니라 어떤 자료형이라도 상관없다. *next는 다음 node를 가리키는 포인터이다. 이렇게 node들로 구성된 연결 리스트는 배열에 비해 확실한 장점을 가진다. 우선 길이의 제한에서 자유롭다. 또 하나는 데이터의 삽입 및 삭제가 쉽다는 것인데 다음 그림을 보면 알 수 있다.
위의 배열 그림을 보면, 데이터를 어디에 추가하려고 할 때 그 뒤에 위치한 데이터들을 다 한 칸씩 뒤로 밀어야 한다는 단점이 있다는 걸 알 수 있다. 반면 연결 리스트는 그런 비효율적인 작업이 불필요하다.
리스트를 가지고 할 수 있는 것들, 즉 리스트의 기능은 기본적으로 다음과 같다.
리스트를 가지고 할 수 있는 것들, 즉 리스트의 기능은 기본적으로 다음과 같다.
1. 데이터의 삽입
2. 데이터의 조회
3. 데이터의 삭제
여기에 하나를 더 추가하자면 데이터의 정렬 정도가 되겠다.
이번 시간에는 데이터의 정렬을 할 수 있는 리스트를 만들어 보려고 하는데, 그 중 dummy node가 들어간 dummy linked list의 구현을 살펴본다. dummy가 들어가는 이유는 구현하면서 설명.
이번 시간에는 데이터의 정렬을 할 수 있는 리스트를 만들어 보려고 하는데, 그 중 dummy node가 들어간 dummy linked list의 구현을 살펴본다. dummy가 들어가는 이유는 구현하면서 설명.
자료구조를 공부할 때에는 1. ADT를 정의하고 2. ADT를 구현하고 3. 구현한 자료구조를 활용하는 세 가지 단계로 학습하라고 했다. 우선 연결 리스트의 ADT를 만들어보자. ADT는 <윤성우의 열혈 자료구조> 123p에서 가져왔다.
1. 리스트 초기화
void ListInit(List* plist);
-초기화할 리스트의 주소 값을 인자로 전달
2. 데이터 저장
void LInsert(List* plist, Ldata data);
-리스트에 데이터 저장
3. 데이터 조회
int LFirst(List* plist, Ldata* pdata);
-첫 번째 데이터가 pdata가 가리키는 메모리에 저장
-참조 성공 시 1, 실패 시 0 반환
int LNext(List* plist, LData* pData);
-참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장됨
-반복 호출 가능
-참조를 시작하려면 LFirst함수를 먼저 호출
-참조 성공 시 1, 실패 시 0 반환
4. 데이터 삭제
LData LRemove(List* plist);
-조회 함수의 마지막 반환 데이터를 삭제함
-반복 호출 안 됨
5. 데이터 수 반환
int LCount(List* plist);
-리스트에 저장된 데이터 수 반환
6. 정렬 관련
void SetSortRule(List* plist, int(*comp)(LData d1, LData d2));
-리스트에 정렬 기준이 되는 함수를 등록
ADT를 정의했으니, 다음 글에서 ADT를 구현해 보자.
댓글 없음:
댓글 쓰기