Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

내가 필요로하는 것이 존재하지 않을 때 다음 두 가지 방법중 하나를 선택해야 한다.

1. 처음부터 새로 만든다.

2. 기존의 것을 활용해서 만든다.

상황에 따라 좋은 선택은 달라지기 마련이다. 마땅히 활용할 대상이 없거나 활용의 결과가 만족스럽지 못하다면 처음부터 새로 만들어야겠지만, 그렇지 않은 경우라면 기존의 것을 활용하는게 훨씬 합리적인 판단일 수 있다.

CLinkedList.c

CLinkedList.h

기능적인 부분만 고려를 한다면 배열은 대부분 연결 리스트로 교체가 가능하다. 배열도 연결 리스트도 기본적인 선형 자료구조이기 때문이다.

head -> data1 -> data2 -> data3 -> NULL

이렇게 메모리 구조만 놓고 보면 이것이 스택을 구현한 것인지, 단순 연결 리스트를 구현한 것인지 알 수 없다.

다만 위의 메모리 구조를 바탕으로 push 연산과 pop 연산이 포함된 ADT를 갖는다면 이것이 스택이 되는 것이다.

스택이란 '쟁반 위에 쌓인 접시', '쌓아 올려진 상자더미' 를 연상할 수 있겠다.

즉, 맨 밑에 상자(제일 먼저 들어간 데이터) 를 꺼내려면 위에 얹혀있는 상자들부터 꺼내야 꺼낼 수 있다. 이것이 바로 스택의 특성이다.

스택은 나중에 들어간 것이 먼저 나오는 구조이다 보니 '후입선출방식의 자료구조' 라고도 불리고, 영어로 'LIFO(Last-In, Fisrt-Out) 구조의 자료구조' 라고도 불린다.

실제로 스택은 쉽게 이해할 수 있고 또 숩게 구현할 수 있는 자료구조이다.

스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 가리켜 각각 push, pop, peek 라고 한다.

void StackInit(Stack * pstack); 

- 스택의 초기화를 진행한다.

- 스택 생성 후 제일 먼저 호출되어야 하는 함수이다.

int IsEmpty(Stack * pstack);

- 스택이 빈 경우 TRUE(1)을 그렇지 않은 경우 FALSE(0)을 반환

void Push(Stack * pstack, Data data);

- 스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장

Data Pop(Stack * pstack);

- 마지막에 저장된 요소를 삭제

- 삭제된 데이터는 반환된다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data Peek(Stack * pstack);

- 마지막에 저장된 요소를 반환하되 삭제하지 않는다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

실행결과에서 입력된 데이터가 역순으로 출력됨을 보이고 있다. 

그리고 이것이 스택의 가장 중요한 특성이다.

데이터를 저장할 때, 리스트의 머리와 꼬리에 각각 더미 노드가 존재하기 때문에 추가의 방법에 있어서 경우의 수가 나뉘지 않는다.

새 노드를 추가할 때의 과정

1. 새 노드를 생성하고 데이터를 저장

2. 새 노드와 새 노드의 왼쪽에 위치할 노드가 서로를 가리키게 한다.

3. 새 노드와 새 노드의 오른쪽에 위치할 노드가 서로를 가리키게 한다.

즉, 이렇게 된다.

               head                                                       tail

                 ↓                                                          ↓

NULL <-  dummy  ->  <-  data1 ->  <-  data2  ->  <-  dummy ->  NULL

이 에러는 보통 할당되었던 메모리가 해제된 상태에서 다시 접근할 때 발생한다.

free() 함수로 메모리를 날려버린 상태에서 다시 포인터가 가리키는 곳의 값을 얻으려하니까 이렇게 에러가 발생하였다.

'양방향 연결 리스트(doubly linked list)' 또는 '이중 연결 리스트' 라고도 불리는 이 자료구조는 그 이름이 의미하듯이 노드가 양쪽 방향으로 연결된 구조의 리스트이다.

즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

ex) data1-> <-data2 -> <-data3

더미 노드 양방향 연걸리스트도 있고, 원형 연결 기반의 양방향 연결 리스트 등등도 있다.

밑에 나오는 예제는 기본적인 양방향 연결 리스트이다.

서로 봐라보는 것이라 복잡하게 느껴진다. 하지만 실제로 코드를 비교해 보면 상대적으로 더 복잡하지 않음을 알 수 있다. 

양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서는 어렵게 구현했던 것이 쉽게 구현되기도 한다. 때문에 오히려 단순하게 느껴지는 측면도 있다.

내 나름대로 원형 연결리스트에 더미노드를 추가해서 바꿔보았다.

바뀐 부분은 붉은색 네모로 표시를 해두었다. 나머지 main함수나 기타등등은 모두 똑같다.

단순 연결 리스트의 마지막 노드는 NULL을 가리켰다. 

그런데, 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 '원형 연결 리스트'가 된다.

이러한 특성 때문에 원형 연결 리스트에서는 머리와 꼬리의 구분이 없다고도 이야기한다. 

원형 연결 리스트의 장점

- 단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다.

이 리스트는 변형된 모델로 알려져 있지만, 실제로는 보다 더 일반적인 모델로 인식된다.

원형 연결 리스트에는 더미 노드가 존재하지 않기 때문에, 삭제에 있어서 다음 두 가지 예외적인 상황을 구분해야 한다.

예외적 상황1    : 삭제할 노드를 tail이 가리키는 경우

예외적 상황2    : 삭제할 노드가 리스트에 홀로 남은 경우

헤더파일

헤더파일의 정의파일

메인함수