이 글은 https://gist.github.com/orionids/734dcb378a116ee10c075220ed626d6a 의 번역본입니다.
영어에 익숙하진 않지만 제가 쓴 글이고, 제 오픈 소스 프로젝트에 신규 도입한 연결 리스트 구조를 설명하기 위해 썼습니다.
리눅스 커널의 해쉬 연결 리스트 관련 내용도 일부 있구요.

공개 gist인데 인기가 없습니다. ( 댓글이 없네요ㅋ -_-; ) 아무튼 우리말로 옮겨봅니다.
그나 저나, 하위 자료 구조를 바꾼 터라, 전체 소스에 적용하기가 좀 귀찮은 상태입니다. =_=

이중 연결 리스트의 헤드 노드 크기 줄이기 (C 언어)

헤드 노드 포인터 사용 시 발생할 수 있는 문제점

범용 연결 리스트를 정의하는 방법 중 하나는 다음과 같고, stddef.h에 정의된 offsetof를 이용하여 하위 구조체를 얻는다.

struct list {
    struct list* next, * prev;
};

리스트의 모든 노드를 반복하기 위해, 첫 (헤드) 노드를 알아야 하므로, 헤드 노드 포인터를 정의하면
 struct list* head = NULL;

다음과 같은 두가지 문제점을 고려해야 한다.

• 연결 리스트가 비어있는 특수한 경우에 대해, 포인터가 NULL인지 확인 필요
  
• 첫 노드 ( 다른 말로는 헤드 노드, 헤드 노드 포인터가 가리키는 노드 )를 제거할 때 헤드 노드 포인터가 필요
  

두 번째 문제점의 예로, 다수의 헤드 노드 포인터로 구성된 해쉬 테이블에서 임의 노드를 삭제하는 경우에 대해 고려해보자.

struct list* head[BUCKETS];

삭제할 노드를 포함하는 리스트의 헤드 노드 포인터를 어떻게 알 수 있을까?
버킷 인덱스나 헤드 노드 포인터에 대한 참조 같은 부가 정보는 필요한 메모리를 증가시킨다.
혹은 해쉬 함수를 계산해서 버킷 인덱스를 얻는 것은 때로 꽤 많은 비용을 필요로 한다.

헤드 노드는 문제점들을 해소하지만, 헤드 노드 크기가 또 다른 이슈가 된다

헤드 노드는 다음과 같이 정의된다.
struct list head = { NULL, NULL };

• &head가 항상 NULL이 아니므로 첫 번째 문제점이 해소된다.
• 전체 리스트를 제거하기 전에는 &head가 변하지 않기 때문에 두 번째 문제점 역시 해소된다.

모든 문제가 해소됐지만, 연결 리스트의 배열 항목이 다수인 경우 헤드 노드 크기가 이슈가 될 수 있다. 해쉬 자료 구조가 이에 해당한다.
헤드 노드 포인터 대신 헤드 노드가 사용된다면 버킷을 위해 두 배의 저장 공간이 필요하다.

struct list hash[BUCKETS];

이를 피하기 위해 리눅스 커널은 hlist 구조체들을 정의한다.

struct hlist_head {
    struct hlist_node *first;
};
 
struct hlist_node {
    struct hlist_node *next, **pprev;
};

이 구조체는 기본적으로 헤드 노드 포인터를 사용 하므로, 위에 언급된 첫 번째 문제점이 hlist_add_head 구현에 드러나 있다.
커널 소스 https://github.com/torvalds/linux/blob/master/include/linux/list.h 참고.

if (first)
		first->pprev = &n->next;

그런데 pprev가 헤드 노드 포인터를 사용할 때 나타나는 두번째 문제점은 해소 시킨다.
hlist_head 구조체의 first에 대한 포인터를 pprev가 저장할 수 있기 때문이다.

하지만, 이러한 구조체들이 범용 연결리스트 구조체와 호환성이 없기 때문에, hlist를 지원하는 추가적인 함수들이 필요하다.
그래서 나는 대안으로, 단일 및 이중 연결 리스트 모두에 호환성 있는 구조체를 정의하는 방법을 제안한다.

단일 및 이중 연결 리스트 모두에 호환되는 연결 리스트 구조체

https://github.com/orionids/Orion/blob/master/coral/def.h 에 정의된 _List 구조체는 다음과 같다 :

struct _List {
    struct _List* link;
};

struct _MyList {
    ...
    struct _List list[2]; // doubly linked list
    ...
};

struct _List* node 에 대해

• node[0].link 또는 node->link 로 다음 노드를 접근한다.
  
• node[1].link 로 이전 노드를 접근한다.

표준이 정의하지 않는 구조체간 포인터 캐스팅 없이 위와 같은 _List 구조체는 단일 및 이중 연결 리스트 모두를 정의할 수 있다.
이러한 개념을 바탕으로 listAdd와 listCut이 https://github.com/orionids/Orion/blob/master/coralsrc/list.c 에 구현되어 있다.

listAddCircularNode 와 listCutCircularNode 는 환형 리스트에 대해 포인터 유효성 확인을 줄인 구현이다.
listAdd 및 listCut이 이 함수들을 대체할 수 있으므로, 소규모 시스템에서는 포함하지 않아도 된다.

이중 연결 리스트에 대해 헤드 노드 크기를 줄이기

해쉬 테이블에 대한 헤드 노드 크기를 줄이기 위해, 단일 연결리스트에 대한 헤드 노드를 사용하면 된다.
이에 의해 리눅스 커널의 hlist와 동일하게, 임의 노드를 삭제할 때 헤드 노드 포인터를 알 필요가 없어진다.
struct _List hash[BUCKETS];

_List구조체는 단일 및 이중 연결 리스트 모두에 호환성있기 때문에,
이중 연결 리스트 함수들이 (&hash[i])[1].link를 접근하지 않는다면, &hash[i] 는 이 함수들에 대한 인자가 될 수 있다.

• listAdd와 listCut이 (&hash[i])[1].link를 접근하지 않도록, 초기에 hash[i].link는 NULL이어야 한다.
• 또는, listCutCircularNode에 대한 약간의 수정은 필요하지만, 환형 리스트 함수들을 사용하기 위해, hash[i].link 는 hash + i ( 환형 노드 )가 될 수 있다. 부적절한 포인터 접근을 피하기 위해, 더미 인자가 적절히 사용된다. ( Coral library에는 구현되어있지 않다. )