단순 연결 리스트 (Single Linked List)

연결 리스트에서 각 요소는 노드(Node)로 이루어 진다.

노드는 구조체로 구현하며, 데이터와 다음 노드를 가리키는 포인터로 이루어 져 있다.

단순 연결 리스트는 이전 노드 안에 있는 포인터가 다음 노드를 가리키는 구조로 되어 있다. 마지막 노드의 링크는 NULL을 가리키며 뒤로 돌아갈 수 없다.

만약 어떤 노드로 돌아가기 원한다면 맨 처음 노드로 다시 설정하여 순회(iteration) 하여야 한다.

연결 리스트를 구현 하는 방법은 두 가지가 있는데,

하나는 더미 노드(Dummy Node)를 이용하는 방법이고 하나는 헤드 포인터(Head Pointer)를 사용하는 방법이다.

더미 노드란, 데이터 저장을 위한 노드가 아니라 노드의 추가/삭제 구현의 간편성을 위해 사용하는 노드이다. 실제 데이터를 저장하는 다른 노드를 가리키는 포인터의 역할만을 수행한다. 

헤드 포인터란, 연결 리스트의 첫 번째 노드를 가리키는 포인터이다. 

더미 노드를 사용하는 방법이 좀 더 구현이 편하고 고려해야 할 수가 적다.

현재 리스트에 존재하고 있는 노드의 개수를 저장하는 변수인 currentElementCount와

헤더 노드(더미 노드 역할)를 가진 연결 리스트 구조체를 만든다.

이해를 돕기 위해 좀 더 그림을 쉽게 표현 해 보았다. 구조체 안에 헤더 노드를 가지고 있어서 노드를 추가하면 헤더 노드의 다음에 추가 되게 된다.

노드의 추가

---

LinkedList 노드를 생성한 후에, 새로운 노드 하나를 동적 할당하여 생성한다.

그리고 그 새로운 노드의 주소값을 헤더노드에 있는 링크에 연결한다.

그러면 헤드 노드의 링크가 새로운 노드를 가리키게 되고, 새로운 노드를 탐색할 수 있게 된다.

노드의 삽입

---

2번째 노드 위치 (position = 1)에 새로운 노드를 삽입한다고 가정해보자. 위치값은 더미노드 다음에 0부터 시작한다 (position >= 0)

새로운 노드를 동적 할당을 통해 생성한다. 물론 생성 후에 data도 초기화 시켜 주어야 한다.

현재 삽입하려는 위치에 있는 노드가 새로 삽입하는 노드의 다음 노드가 된다.

그러므로 삽입하려는 위치 하나 이전에 위치한 노드 까지 반복문을 통해서 포인터 링크를 타고 이동한다.

코드로 예를 들면 이러하다.

    int position = 1;
 
    LinkedListNode pPreNode = &(LinkedList->headerNode);
 
    for (i = 0; i < position; i++) {
 
        pPreNode = pPreNode->pLink;
 
    }

헤더노드 부터 이동한다는 점을 염두에 두자. 헤드 포인터를 사용한다면 지금 조건문에서 멈추는 곳은 2번째 위치지만, 우리는 지금 더미 노드를 사용하므로 1번째 위치에서 멈추게 된다.

우선 새로운 노드의 링크가 가리키는 곳을 현재 이동시킨 커서, 즉 첫번째 위치에 있는 노드(position-1에 있는 노드)가 가리키는 곳으로 설정한다.

그리고 이동 시킨 커서(position-1)이 가리키는 다음으로 새로운 노드를 설정한다.

이것을 코드로 보면 아래와 같다.

pNewNode->pLink = pPreNode->pLink;
pPreNode->pLink = pNewNode;

노드의 삭제

---

아까와 같이 2번째 자리(position = 1)에 있는 노드를 이번에는 삭제 한다고 가정 해보자.

반복문을 통해 삭제할 노드의 이전 노드로 이동한다. (position-1, preNode)

그리고 삭제할 노드는 deleteNode로 설정한다.

삭제할 노드의 이전 노드(preNode)의 링크가 가리크는 곳을 삭제할 노드가 가리키는 곳으로 설정한다.

그리고 deleteNode는 메모리 해제 시켜주면 된다. 이것을 코드로 나타내면 아래와 같다.

pPreNode->pLink = pDelNode->pLink;
free(pDelNode);

나머지 함수들은 리스트의 ADT를 보면서 구현하면 된다.

연결 리스트는 포인터 링크를 따라 연결되어 있는 구조라는 것을 이해하면 쉽게 구현이 가능하다.