1.1. 시작하기에 앞서
LinkedList(연결리스트)는 자료의 집합을 관리하는데 있어서 각 자료들을 pointer(포인터)로 연관지어 관리하는 방식이다. 자료의 공간을 미리 최대 공간만큼 확보하지 않고 순차적으로 추가, 삭제, 삽입을 저렴한 비용으로 유지할수 있어 많이 사용되고 있으나 검색을 하는데에 있어서는 자료수(n)만큼 걸리는 단점이 있다.
LinkedList(연결리스트)는 크게 Singly Linked List (단순 연결 리스트, 단방향 연결 리스트)와 Doubly Linked List (이중 연결 리스트, 쌍방향 연결 리스트) 그리고 Circular Linked List (원형 연결 리스트) 등이 있다.
LinkedList(연결리스트)는 크게 Singly Linked List (단순 연결 리스트, 단방향 연결 리스트)와 Doubly Linked List (이중 연결 리스트, 쌍방향 연결 리스트) 그리고 Circular Linked List (원형 연결 리스트) 등이 있다.
1.2. 운영에 필요한 요소
자료의 시작을 가르키는 head pointer와 끝을 가르키는 tail pointer의 요소가 있으며 경우에 따라서는 head pointer와 tail pointer중에 한가지만 가지고 운영하는 경우도 있다. 아래 예제에서는 tail pointer를 운영하는 경우와 하지 않는 경우 모두를 고려하여 실제로 사용가능한 형태로 구현하여 제시된다. 실제로 필자는 이 코드를 사용하기는 하지만 실제 release시점이 되면 macro 구현을 모두 풀어헤치고 최적화하여 macro 없이 사용하게 된다. 구현할때 구현 자체에 집중하기 위해서 이러한 macro를 이용하여 초기에 설계하고 작성하면 도움이 된다.
동작요소로는 하나의 자료를 선두에 삽입하는 prepend, 맨뒤에 삽입하는 append, 특정 자료의 앞이나 뒤에 삽입하는 insert, 운영과정에서 정렬된 순서로 삽입하는 sort insert, 특정 자료를 삭제하는 delete, 특정 자료를 교환하는 replace, 자료들을 특정 조건에 따라 정렬하는 sort, 그리고 자료의 갯수를 파악하기 위한 get_count, 자료의 순번을 확인하는 index, 자료를 검색하는 search 등을 구현할수 있어야 한다.
![[https]](https://www.minzkn.com:443/moniwiki/imgs/https.png)
uthash![[]](/moniwiki/imgs/moni2/external.png)
(https://github.com/troydhanson/uthash) 같은 공개프로젝트에서 제공되는 utlist.h header를 한번쯤 보면 좋다. 물론 필자가 아래에 구현한 예제는 utlist.h 가 바라보는 pointer의 시점과 약간 다르지만 문맥은 거의 비슷하다.
동작요소로는 하나의 자료를 선두에 삽입하는 prepend, 맨뒤에 삽입하는 append, 특정 자료의 앞이나 뒤에 삽입하는 insert, 운영과정에서 정렬된 순서로 삽입하는 sort insert, 특정 자료를 삭제하는 delete, 특정 자료를 교환하는 replace, 자료들을 특정 조건에 따라 정렬하는 sort, 그리고 자료의 갯수를 파악하기 위한 get_count, 자료의 순번을 확인하는 index, 자료를 검색하는 search 등을 구현할수 있어야 한다.
uthash(https://github.com/troydhanson/uthash) 같은 공개프로젝트에서 제공되는 utlist.h header를 한번쯤 보면 좋다. 물론 필자가 아래에 구현한 예제는 utlist.h 가 바라보는 pointer의 시점과 약간 다르지만 문맥은 거의 비슷하다.
1.3. 예제소스에 필요한 사전 구현사항
아래 예제를 구현하기 위하여 기본적으로 몇가지 사전에 구현해두어야 하는게 있어서 다음과 같이 정리합니다. 또한 아래는 C언어의 Macro로 구현하였지만 이 구현 그대로 사용하게 되면 일부 구버젼의 컴파일러 환경에서 Pointer의 Align 대응에 문제가 있을수 있는 사항이 있으니 함수화 하여 사용하는게 문제의 소지를 줄일수 있다는 점 유의 하면서 읽어주세요.
/* 주어진 구조체 자료형 _m_type의 멤머변수 _m_member의 offset 을 반환 */
#define hwport_offsetof(_m_type,_m_member) ((size_t)(&((_m_type *)0)->_m_member))
#define hwport_peek_vector(m_cast,m_base,m_sign,m_offset) ((m_cast)((void *)(((hwport_uint8_t *)(m_base)) m_sign ((size_t)(m_offset)))))
#define hwport_peek_f(m_cast,m_base,m_offset) hwport_peek_vector(m_cast,m_base,+,m_offset)
/* pointer m_from으로부터 m_offset(byte단위) 위치의 값을 m_cast만큼 얻는다 */
#define hwport_peek_type(m_cast,m_from,m_offset) (*(hwport_peek_f(m_cast *,m_from,m_offset)))
/* pointer m_from으로부터 m_offset(byte단위) 위치에 m_value값을 m_cast만큼 저장 */
#define hwport_poke_type(m_cast,m_to,m_offset,m_value) do{hwport_peek_type(m_cast,m_to,m_offset)=(m_cast)(m_value);}while(0)
/* sort와 search에 필요한 자료의 조건을 판단하기 위한 callback 함수 pointer */
#if !defined(hwport_compare_linked_list_handler_t)
/* result = left - right; => 결과값이 음수인 경우 left 가 선두로 배치되는 운영방식 */
typedef int (*__hwport_compare_linked_list_handler_t)(void * /* s_left_element */, void * /* s_right_element */);
# define hwport_compare_linked_list_handler_t __hwport_compare_linked_list_handler_t
#endif
1.4. Singly Linked List (단순 연결 리스트, 단방향 연결 리스트)
- prepend
#define __hwport_singly_linked_list_prepend(_m_head_ptr,_m_tail_ptr,_m_element,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ hwport_poke_type(void *,_m_element,(_m_next_offset),*(_m_head_ptr));\ if(_sm_tail_ptr != ((void **)0)) {\ if((*(_m_head_ptr)) == ((void *)0)) { *_sm_tail_ptr = (_m_element); }\ }\ *(_m_head_ptr) = (_m_element);\ }while(0) - append
#define __hwport_singly_linked_list_append(_m_head_ptr,_m_tail_ptr,_m_element,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ if(_sm_tail_ptr != ((void **)0)) {\ if((*_sm_tail_ptr) == ((void *)0)) { *(_m_head_ptr) = (_m_element); }\ else { hwport_poke_type(void *,*_sm_tail_ptr,(_m_next_offset),(_m_element)); }\ *_sm_tail_ptr = (_m_element);\ }\ else if((*(_m_head_ptr)) == ((void *)0)) { *(_m_head_ptr) = (_m_element); }\ else {\ void *_sm_next, *_sm_trace;\ for(_sm_trace = (*(_m_head_ptr));;) {\ _sm_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_next == ((void *)0)) { break; }\ _sm_trace = _sm_next;\ }\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),(_m_element));\ }\ }while(0) - delete
#define __hwport_singly_linked_list_delete(_m_head_ptr,_m_tail_ptr,_m_element,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ if((*(_m_head_ptr)) == (_m_element)) {\ *(_m_head_ptr) = hwport_peek_type(void *,(_m_element),(_m_next_offset));\ if(_sm_tail_ptr != ((void **)0)) {\ if((*(_m_tail_ptr)) == (_m_element)) { *_sm_tail_ptr = (void *)0; }\ }\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ }\ else {\ void *_sm_next, *_sm_trace;\ for(_sm_trace = (*(_m_head_ptr));;) {\ _sm_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_next == ((void *)0)) { break; }\ if(_sm_next == ((void *)(_m_element))) {\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),hwport_peek_type(void *,(_m_element),(_m_next_offset)));\ if(_sm_tail_ptr != ((void **)0)) {\ if((*_sm_tail_ptr) == (_m_element)) { *_sm_tail_ptr = _sm_trace; }\ }\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ break;\ }\ _sm_trace = _sm_next;\ }\ }\ }while(0) - replace
#define __hwport_singly_linked_list_replace(_m_head_ptr,_m_tail_ptr,_m_element,_m_new_element,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),hwport_peek_type(void *,(_m_element),(_m_next_offset)));\ if((*(_m_head_ptr)) == (_m_element)) {\ *(_m_head_ptr) = (_m_new_element);\ if(_sm_tail_ptr != ((void **)0)) {\ if((*(_m_tail_ptr)) == (_m_element)) { *_sm_tail_ptr = (_m_new_element); }\ }\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ }\ else {\ void *_sm_next, *_sm_trace;\ for(_sm_trace = (*(_m_head_ptr));;) {\ _sm_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_next == ((void *)0)) { break; }\ if(_sm_next == ((void *)(_m_element))) {\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),(_m_new_element));\ if(_sm_tail_ptr != ((void **)0)) {\ if((*_sm_tail_ptr) == (_m_element)) { *_sm_tail_ptr = (_m_new_element); }\ }\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ break;\ }\ _sm_trace = _sm_next;\ }\ }\ }while(0) - insert
#define __hwport_singly_linked_list_insert(_m_head_ptr,_m_tail_ptr,_m_element,_m_new_element,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ (void)_sm_tail_ptr;\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),(_m_element));\ if((*(_m_head_ptr)) == (_m_element)) { *(_m_head_ptr) = (_m_new_element); }\ else {\ void *_sm_next, *_sm_trace;\ for(_sm_trace = (*(_m_head_ptr));;) {\ _sm_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_next == ((void *)0)) { break; }\ if(_sm_next == ((void *)(_m_element))) {\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),(_m_new_element));\ break;\ }\ _sm_trace = _sm_next;\ }\ }\ }while(0) - sort insert
#define __hwport_singly_linked_list_sort_insert(_m_head_ptr,_m_tail_ptr,_m_new_element,_m_next_offset,_m_compare_handler) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ hwport_compare_linked_list_handler_t _sm_compare_handler = (_m_compare_handler);\ if((*(_m_head_ptr)) == ((void *)0)) {\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),(void *)0);\ *(_m_head_ptr) = (_m_new_element);\ if(_sm_tail_ptr != ((void **)0)) { *(_sm_tail_ptr) = (_m_new_element); }\ }\ else {\ void *_sm_prev, *_sm_next, *_sm_trace;\ for(_sm_prev = (void *)0, _sm_trace = (*(_m_head_ptr));;) {\ if((*_sm_compare_handler)((_m_new_element),_sm_trace) < 0) {\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),_sm_trace);\ if(_sm_prev == ((void *)0)) { *(_m_head_ptr) = (_m_new_element); }\ else { hwport_poke_type(void *,_sm_prev,(_m_next_offset),(_m_new_element)); }\ break;\ }\ _sm_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_next == ((void *)0)) {\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),(void *)0);\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),(_m_new_element));\ if(_sm_tail_ptr != ((void **)0)) { *(_sm_tail_ptr) = (_m_new_element); }\ break;\ }\ _sm_prev = _sm_trace;\ _sm_trace = _sm_next;\ }\ }\ }while(0) - sort
#define __hwport_singly_linked_list_sort(_m_head_ptr,_m_tail_ptr,_m_next_offset,_m_compare_handler) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ if((*(_m_head_ptr)) != ((void *)0)) {\ void *_sm_trace, *_sm_trace_prev, *_sm_trace_next, *_sm_trace_next_next;\ int _sm_is_swapped;\ do {\ _sm_is_swapped = 0; _sm_trace = *(_m_head_ptr); _sm_trace_prev = (void *)0;\ for(;;) {\ _sm_trace_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_trace_next == ((void *)0)) { break; }\ if((_m_compare_handler)(_sm_trace,_sm_trace_next) > 0) {\ _sm_is_swapped = 1;\ _sm_trace_next_next = hwport_peek_type(void *,_sm_trace_next,(_m_next_offset));\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),_sm_trace_next_next);\ hwport_poke_type(void *,_sm_trace_next,(_m_next_offset),_sm_trace);\ if(_sm_trace_prev != ((void *)0)) { hwport_poke_type(void *,_sm_trace_prev,(_m_next_offset),_sm_trace_next); }\ _sm_trace_prev = _sm_trace_next;\ if((*(_m_head_ptr)) == _sm_trace) { *(_m_head_ptr) = _sm_trace_next; }\ if(_sm_tail_ptr != ((void **)0)) {\ if(_sm_trace_next_next == ((void *)0)) { *_sm_tail_ptr = _sm_trace; }\ }\ }\ else { _sm_trace_prev = _sm_trace; _sm_trace = _sm_trace_next; }\ }\ }while(_sm_is_swapped != 0);\ }\ }while(0)
1.5. Doubly Linked List (이중 연결 리스트, 쌍방향 연결 리스트)
- prepend
#define __hwport_doubly_linked_list_prepend(_m_head_ptr,_m_tail_ptr,_m_element,_m_prev_offset,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ hwport_poke_type(void *,_m_element,(_m_prev_offset),(void *)0);\ hwport_poke_type(void *,_m_element,(_m_next_offset),*(_m_head_ptr));\ if((*(_m_head_ptr)) != ((void *)0)) { hwport_poke_type(void *,*(_m_head_ptr),(_m_prev_offset),(_m_element)); }\ if(_sm_tail_ptr != ((void **)0)) {\ if((*(_m_head_ptr)) == ((void *)0)) { *_sm_tail_ptr = (_m_element); }\ }\ *(_m_head_ptr) = (_m_element);\ }while(0) - append
#define __hwport_doubly_linked_list_append(_m_head_ptr,_m_tail_ptr,_m_element,_m_prev_offset,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ if(_sm_tail_ptr != ((void **)0)) {\ hwport_poke_type(void *,(_m_element),(_m_prev_offset),*_sm_tail_ptr);\ if((*_sm_tail_ptr) == ((void *)0)) { *(_m_head_ptr) = (_m_element); }\ else { hwport_poke_type(void *,*_sm_tail_ptr,(_m_next_offset),(_m_element)); }\ *_sm_tail_ptr = (_m_element);\ }\ else if((*(_m_head_ptr)) == ((void *)0)) {\ hwport_poke_type(void *,(_m_element),(_m_prev_offset),(void *)0);\ *(_m_head_ptr) = (_m_element);\ }\ else {\ void *_sm_next, *_sm_trace;\ for(_sm_trace = (*(_m_head_ptr));;) {\ _sm_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_next == ((void *)0)) { break; }\ _sm_trace = _sm_next;\ }\ hwport_poke_type(void *,(_m_element),(_m_prev_offset),_sm_trace);\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),(_m_element));\ }\ }while(0) - delete
#define __hwport_doubly_linked_list_delete(_m_head_ptr,_m_tail_ptr,_m_element,_m_prev_offset,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ void *_sm_prev = hwport_peek_type(void *,(_m_element),(_m_prev_offset)), *_sm_next = hwport_peek_type(void *,(_m_element),(_m_next_offset));\ if(_sm_prev == ((void *)0)) { *(_m_head_ptr) = _sm_next; }\ else { hwport_poke_type(void *,_sm_prev,(_m_next_offset),_sm_next); }\ if(_sm_next == ((void *)0)) {\ if(_sm_tail_ptr != ((void **)0)) { *_sm_tail_ptr = _sm_prev; }\ }\ else { hwport_poke_type(void *,_sm_next,(_m_prev_offset),_sm_prev); }\ hwport_poke_type(void *,(_m_element),(_m_prev_offset),(void *)0);\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ }while(0) - replace
#define __hwport_doubly_linked_list_replace(_m_head_ptr,_m_tail_ptr,_m_element,_m_new_element,_m_prev_offset,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ void *_sm_prev = hwport_peek_type(void *,(_m_element),(_m_prev_offset)), *_sm_next = hwport_peek_type(void *,(_m_element),(_m_next_offset));\ hwport_poke_type(void *,(_m_new_element),(_m_prev_offset),_sm_prev);\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),_sm_next);\ if(_sm_prev == ((void *)0)) { *(_m_head_ptr) = (_m_new_element); }\ else { hwport_poke_type(void *,_sm_prev,(_m_next_offset),(_m_new_element)); }\ if(_sm_next == ((void *)0)) {\ if(_sm_tail_ptr != ((void **)0)) { *_sm_tail_ptr = (_m_new_element); }\ }\ else { hwport_poke_type(void *,_sm_next,(_m_prev_offset),(_m_new_element)); }\ hwport_poke_type(void *,(_m_element),(_m_prev_offset),(void *)0);\ hwport_poke_type(void *,(_m_element),(_m_next_offset),(void *)0);\ }while(0) - insert
#define __hwport_doubly_linked_list_insert(_m_head_ptr,_m_tail_ptr,_m_element,_m_new_element,_m_prev_offset,_m_next_offset) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ void *_sm_prev = hwport_peek_type(void *,(_m_element),(_m_prev_offset));\ (void)_sm_tail_ptr;\ hwport_poke_type(void *,(_m_element),(_m_prev_offset),(_m_new_element));\ hwport_poke_type(void *,(_m_new_element),(_m_prev_offset),_sm_prev);\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),(_m_element));\ if(_sm_prev == ((void *)0)) { *(_m_head_ptr) = (_m_new_element); }\ else { hwport_poke_type(void *,_sm_prev,(_m_next_offset),(_m_new_element)); }\ }while(0) - sort insert
#define __hwport_doubly_linked_list_sort_insert(_m_head_ptr,_m_tail_ptr,_m_new_element,_m_prev_offset,_m_next_offset,_m_compare_handler) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ hwport_compare_linked_list_handler_t _sm_compare_handler = (_m_compare_handler);\ if((*(_m_head_ptr)) == ((void *)0)) {\ hwport_poke_type(void *,(_m_new_element),(_m_prev_offset),(void *)0);\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),(void *)0);\ *(_m_head_ptr) = (_m_new_element);\ if(_sm_tail_ptr != ((void **)0)) { *(_sm_tail_ptr) = (_m_new_element); }\ }\ else {\ void *_sm_prev, *_sm_next, *_sm_trace;\ for(_sm_trace = (*(_m_head_ptr));;) {\ if((*_sm_compare_handler)((_m_new_element),_sm_trace) < 0) {\ _sm_prev = hwport_peek_type(void *,_sm_trace,(_m_prev_offset));\ hwport_poke_type(void *,(_m_new_element),(_m_prev_offset),_sm_prev);\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),_sm_trace);\ if(_sm_prev == ((void *)0)) { *(_m_head_ptr) = (_m_new_element); }\ else { hwport_poke_type(void *,_sm_prev,(_m_next_offset),(_m_new_element)); }\ hwport_poke_type(void *,_sm_trace,(_m_prev_offset),(_m_new_element));\ break;\ }\ _sm_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_next == ((void *)0)) {\ hwport_poke_type(void *,(_m_new_element),(_m_prev_offset),_sm_trace);\ hwport_poke_type(void *,(_m_new_element),(_m_next_offset),(void *)0);\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),(_m_new_element));\ if(_sm_tail_ptr != ((void **)0)) { *(_sm_tail_ptr) = (_m_new_element); }\ break;\ }\ _sm_trace = _sm_next;\ }\ }\ }while(0) - sort
#define __hwport_doubly_linked_list_sort(_m_head_ptr,_m_tail_ptr,_m_prev_offset,_m_next_offset,_m_compare_handler) \ do {\ void **_sm_tail_ptr = (void **)(_m_tail_ptr);\ if((*(_m_head_ptr)) != ((void *)0)) {\ void *_sm_trace, *_sm_trace_prev, *_sm_trace_next, *_sm_trace_next_next;\ int _sm_is_swapped;\ do {\ _sm_is_swapped = 0; _sm_trace = *(_m_head_ptr); _sm_trace_prev = (void *)0;\ for(;;) {\ _sm_trace_next = hwport_peek_type(void *,_sm_trace,(_m_next_offset));\ if(_sm_trace_next == ((void *)0)) { break; }\ if((_m_compare_handler)(_sm_trace,_sm_trace_next) > 0) {\ _sm_is_swapped = 1;\ _sm_trace_next_next = hwport_peek_type(void *,_sm_trace_next,(_m_next_offset));\ if(_sm_trace_next_next != ((void *)0)) { hwport_poke_type(void *,_sm_trace_next_next,(_m_prev_offset),_sm_trace); }\ hwport_poke_type(void *,_sm_trace,(_m_next_offset),_sm_trace_next_next);\ hwport_poke_type(void *,_sm_trace,(_m_prev_offset),_sm_trace_next);\ hwport_poke_type(void *,_sm_trace_next,(_m_next_offset),_sm_trace);\ hwport_poke_type(void *,_sm_trace_next,(_m_prev_offset),_sm_trace_prev);\ if(_sm_trace_prev != ((void *)0)) { hwport_poke_type(void *,_sm_trace_prev,(_m_next_offset),_sm_trace_next); }\ _sm_trace_prev = _sm_trace_next;\ if((*(_m_head_ptr)) == _sm_trace) { *(_m_head_ptr) = _sm_trace_next; }\ if(_sm_tail_ptr != ((void **)0)) {\ if(_sm_trace_next_next == ((void *)0)) { *_sm_tail_ptr = _sm_trace; }\ }\ }\ else { _sm_trace_prev = _sm_trace; _sm_trace = _sm_trace_next; }\ }\ }while(_sm_is_swapped != 0);\ }\ }while(0);
1.6. Circular Linked List (원형 연결 리스트)
각자 응용해서 만들어 보기를...
- prepend
/* ... */
- append
/* ... */
- delete
/* ... */
- replace
/* ... */
- insert
/* ... */
- sort
/* ... */
1.7. 사용예제
- 예제를 확인하기 위한 기본함수
static int __hwport_compare(void *s_left, void *s_right) { return(hwport_strcmp(hwport_peek_type(char *, s_left, 0), hwport_peek_type(char *, s_right, 0)); } static ssize_t hwport_linked_list_index(void **s_head_or_tail_ptr, void *s_element, size_t s_next_or_prev_offset) { ssize_t s_index; void *s_trace; for(s_index = (ssize_t)0, s_trace = (*s_head_or_tail_ptr);s_trace != ((void *)0);s_trace = hwport_peek_type(void *, s_trace, s_next_or_prev_offset), s_index++) { if(s_trace == s_element) { return(s_index); } } return((ssize_t)(-1)); } static ssize_t hwport_linked_list_count(void **s_head_or_tail_ptr, size_t s_next_or_prev_offset, const char *s_file) { ssize_t s_index; void *s_trace; for(s_index = (ssize_t)0, s_trace = (*s_head_or_tail_ptr);s_trace != ((void *)0);s_trace = hwport_peek_type(void *, s_trace, s_next_or_prev_offset), s_index++); return(s_index); } - Singly Linked List (단순 연결 리스트, 단방향 연결 리스트) 구현예제
struct hwport_singly_linked_list_test_ts { const char *m_string; struct hwport_singly_linked_list_test_ts *m_next; } *s_head = (struct hwport_singly_linked_list_test_ts *)0, *s_tail = (struct hwport_singly_linked_list_test_ts *)0, s_node[6], *s_trace; size_t s_next_offset = hwport_offsetof(struct hwport_singly_linked_list_test_ts, m_next); s_node[0].m_string = "hello"; s_node[1].m_string = "a world"; s_node[2].m_string = "test"; s_node[3].m_string = "singlylist"; s_node[4].m_string = "insertitem"; s_node[5].m_string = "insertitem2"; hwport_singly_linked_list_append(&s_head, &s_tail, &s_node[0], s_next_offset); ASSERT((s_head == (&s_node[0])) && (s_tail == (&s_node[0]))); hwport_singly_linked_list_append(&s_head, &s_tail, &s_node[1], s_next_offset); ASSERT((s_head == (&s_node[0])) && (s_tail == (&s_node[1]))); hwport_singly_linked_list_append(&s_head, &s_tail, &s_node[2], s_next_offset); ASSERT((s_head == (&s_node[0])) && (s_tail == (&s_node[2]))); hwport_singly_linked_list_prepend(&s_head, &s_tail, &s_node[3], s_next_offset); ASSERT((s_head == (&s_node[3])) && (s_tail == (&s_node[2]))); hwport_singly_linked_list_delete(&s_head, &s_tail, &s_node[2], s_next_offset); ASSERT((s_head == (&s_node[3])) && (s_tail == (&s_node[1]))); ASSERT(s_node[2].m_next == ((struct hwport_singly_linked_list_test_ts *)0)); hwport_singly_linked_list_replace(&s_head, &s_tail, &s_node[0], &s_node[2], s_next_offset); ASSERT(s_node[0].m_next == ((struct hwport_singly_linked_list_test_ts *)0)); hwport_singly_linked_list_replace(&s_head, &s_tail, &s_node[2], &s_node[0], s_next_offset); ASSERT(s_node[2].m_next == ((struct hwport_singly_linked_list_test_ts *)0)); hwport_singly_linked_list_insert(&s_head, &s_tail, &s_node[0], &s_node[4], s_next_offset); hwport_singly_linked_list_insert(&s_head, &s_tail, &s_node[3], &s_node[5], s_next_offset); ASSERT((s_head == (&s_node[5])) && (s_tail == (&s_node[1]))); for(s_trace = s_head;s_trace != ((struct hwport_singly_linked_list_test_ts *)0);s_trace = s_trace->m_next) { (void)printf("forward data[%ld]: \"%s\"\n", (long)hwport_linked_list_index(&s_head, s_trace, s_next_offset), s_trace->m_string); } hwport_singly_linked_list_sort(&s_head, &s_tail, s_next_offset, (hwport_compare_linked_list_handler_t)__hwport_compare); for(s_trace = s_head;s_trace != ((struct hwport_singly_linked_list_test_ts *)0);s_trace = s_trace->m_next) { (void)printf("sorted forward data[%ld]: \"%s\"\n", (long)hwport_linked_list_index(&s_head, s_trace, s_next_offset), s_trace->m_string); } s_trace = s_tail; (void)printf("sorted tail data[%ld]: \"%s\"\n", (long)hwport_linked_list_index(&s_head, s_trace, s_next_offset), s_trace->m_string); (void)printf("total singly linked list : %ld\n", (long)hwport_linked_list_count(&s_head, s_next_offset)); - Doubly Linked List (이중 연결 리스트, 쌍방향 연결 리스트) 구현예제
struct hwport_doubly_linked_list_test_ts { const char *m_string; struct hwport_doubly_linked_list_test_ts *m_prev; struct hwport_doubly_linked_list_test_ts *m_next; } *s_head = (struct hwport_doubly_linked_list_test_ts *)0, *s_tail = (struct hwport_doubly_linked_list_test_ts *)0, s_node[6], *s_trace; size_t s_prev_offset = hwport_offsetof(struct hwport_doubly_linked_list_test_ts, m_prev); size_t s_next_offset = hwport_offsetof(struct hwport_doubly_linked_list_test_ts, m_next); s_node[0].m_string = "hello"; s_node[1].m_string = "a world"; s_node[2].m_string = "test"; s_node[3].m_string = "doublylist"; s_node[4].m_string = "insertitem"; s_node[5].m_string = "insertitem2"; hwport_doubly_linked_list_append(&s_head, &s_tail, &s_node[0], s_prev_offset, s_next_offset); ASSERT((s_head == (&s_node[0])) && (s_tail == (&s_node[0]))); hwport_doubly_linked_list_append(&s_head, &s_tail, &s_node[1], s_prev_offset, s_next_offset); ASSERT((s_head == (&s_node[0])) && (s_tail == (&s_node[1]))); hwport_doubly_linked_list_append(&s_head, &s_tail, &s_node[2], s_prev_offset, s_next_offset); ASSERT((s_head == (&s_node[0])) && (s_tail == (&s_node[2]))); hwport_doubly_linked_list_prepend(&s_head, &s_tail, &s_node[3], s_prev_offset, s_next_offset); ASSERT((s_head == (&s_node[3])) && (s_tail == (&s_node[2]))); hwport_doubly_linked_list_delete(&s_head, &s_tail, &s_node[2], s_prev_offset, s_next_offset); ASSERT((s_head == (&s_node[3])) && (s_tail == (&s_node[1]))); ASSERT(s_node[2].m_next == ((struct hwport_doubly_linked_list_test_ts *)0)); hwport_doubly_linked_list_replace(&s_head, &s_tail, &s_node[0], &s_node[2], s_prev_offset, s_next_offset); ASSERT(s_node[0].m_next == ((struct hwport_doubly_linked_list_test_ts *)0)); hwport_doubly_linked_list_replace(&s_head, &s_tail, &s_node[2], &s_node[0], s_prev_offset, s_next_offset); ASSERT(s_node[2].m_next == ((struct hwport_doubly_linked_list_test_ts *)0)); hwport_doubly_linked_list_insert(&s_head, &s_tail, &s_node[0], &s_node[4], s_prev_offset, s_next_offset); hwport_doubly_linked_list_insert(&s_head, &s_tail, &s_node[3], &s_node[5], s_prev_offset, s_next_offset); ASSERT((s_head == (&s_node[5])) && (s_tail == (&s_node[1]))); for(s_trace = s_head;s_trace != ((struct hwport_doubly_linked_list_test_ts *)0);s_trace = s_trace->m_next) { (void)printf("forward data[%ld]: \"%s\"\n", (long)hwport_linked_list_index(&s_head, s_trace, s_next_offset), s_trace->m_string); } for(s_trace = s_tail;s_trace != ((struct hwport_doubly_linked_list_test_ts *)0);s_trace = s_trace->m_prev) { (void)printf("backward data[%ld]: \"%s\"\n", (long)hwport_linked_list_index(&s_head, s_trace, s_next_offset), s_trace->m_string); } hwport_doubly_linked_list_sort(&s_head, &s_tail, s_prev_offset, s_next_offset, (hwport_compare_linked_list_handler_t)__hwport_compare); for(s_trace = s_head;s_trace != ((struct hwport_doubly_linked_list_test_ts *)0);s_trace = s_trace->m_next) { (void)printf("sorted forward data[%ld]: \"%s\"\n", (long)hwport_linked_list_index(&s_head, s_trace, s_next_offset), s_trace->m_string); } for(s_trace = s_tail;s_trace != ((struct hwport_doubly_linked_list_test_ts *)0);s_trace = s_trace->m_prev) { (void)printf("sorted backward data[%ld]: \"%s\"\n", (long)hwport_linked_list_index(&s_head, s_trace, s_next_offset), s_trace->m_string); } (void)printf("total doubly linked list : %ld\n", (long)hwport_linked_list_count(&s_head, s_next_offset)); (void)printf("total doubly linked list(r) : %ld\n", (long)hwport_linked_list_count(&s_tail, s_prev_offset));