연결 리스트 ( linked list ) 는 가장 기본적인 자료 구조 중 하나이다. 연결 리스트는 특정 순서로 연결된 여러 개의 자료들로 이루어진다. 일련의 자료들을 다루는 데 배열이 유용한 것처럼 연결 리스트도 그러한 자료를 관리하는데 유용하다. 그러나 배열과 비교할 때 연결 리스트에는 여러 면에서 중요한 장점들이 있다. 특히 삽입과 삭제를 수행하는데 매우 효율적이다. 또 연결 리스트는 실행 중에 할당되는 동적 할당 메모리를 사용한다. 많은 애플리케이션에서 자료의 크기를 컴파일 시간에 알 수 없기 때문에 이것은 좋은 특징이 될 수 있다.
이 장에서 다루는 것들은 다음과 같다.
단일 연결 리스트
각 항목들이 하나의 포인터로 연결된 가장 단순한 연결 리스트다. 리스트의 첫 항목부터 마지막 항목까지 순회할 수 있다.
이중 연결 리스트
각 항목들이 두 개의 포인터로 연결된 연결 리스트다. 양 방향으로 순회할 수 있다.
원형 리스트
마지막 항목의 포인터가 NULL 대신에 첫 항목을 가리키는 연결 리스트다. 리스트를 원형으로 순회할 수 있다.
연결리스트의 어플리케이션들은 다음과 같다.
메일링 리스트
전자우편 애플리케이션에 사용되는 리스트다. 메일링 리스트(mailing lists)의 길이를 예측하기 어려우므로 송신자는 메시지를 보내기 전에 주소의 연결 리스트를 만든다.
스크롤되는 리스트
GUI(Graphickal User Interfaces)에서 볼 수 있는 컴포넌트다.
스크롤되는 리스트(scrolled lists)의 자료들은 흔히 보여지지 않는다. 이러한 "가려진" 자료를 관리하는 한 가지 방법이 스크롤되는 리스트의 항목들을 연결 리스트로 관리하는 것이다.
다항식
대부분의 언어에서 기본 데이터 타입으로 제공되지 않는 수학의 중요한 분야이다. 연결 리스트의 항목에 각 항을 저장하면 연결 리스트는 다항식을 표현하는데 유용하게 사용될 수 있다. (3x^2 + 2x + 1과 같은 경우)
메모리 관리
운영체제의 중요한 역할이다. 운영체제에는 프로세스들을 위해 메모리를 할당하고 해제하는 방법이 있어야 한다. 할당 가능한 메모리 영역을 관리하는 데 연결 리스트를 사용할 수 있다. 이 부분은 이 장에서 다루어질 것이다.
LISP
인공지능(artificial intelligence) 분야에서 사용되는 중요한 프로그래밍 언어이다. LISP은 리스트 처리(LiSt Processor)의 약자로서 기호 처리를 위해 연결 리스트를 많이 사용한다.
파일의 연결된 할당
디스크에서 외부 손실은 없지만 순차적인 접근일 때만 유용한 파일 할당 방법이다. 파일의 각 블록은 다음 블록에 대한 포인터를 포함한다.
다른 자료 구조들
연결 리스트를 이용해 구현을 하는 자료 구조들로 스택, 큐, 집합, 해시 테이블, 그래프 등이 있는데 모두 이 책에서 다루어진다.
연결 리스트의 구현
List.h
#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
// 연결 리스트 항목들의 구조체 정의.
typedef struct ListElmt_
{
void *data;
struct ListElmt_ *next;
}ListElmt;
// 연결 리스트 구조체 정의
typedef struct List_
{
int size;
int (*match)(const void* key1, const void* key2);
void (*destroy)(void *data);
ListElmt *head;
ListElmt *tail;
}List;
'Programming' 카테고리의 다른 글
| freetype library (0) | 2007/12/14 |
|---|---|
| rand(), srand(), RAND_MAX (0) | 2007/11/10 |
| 맵핑이란.. Mapping (0) | 2007/10/05 |
| ID3DXSprite::Begin (0) | 2007/10/02 |
| D3DXCreateSprite (0) | 2007/09/30 |
| 연결 리스트 ( Linked List ) 링크드 리스트 (0) | 2007/09/23 |
| 순열(next_permutation)과 문자열 변환 (0) | 2007/09/16 |
| next_permutation (0) | 2007/09/13 |
| DICamera (0) | 2007/06/19 |
| Camera Class 구현 (0) | 2007/06/19 |
| DirectX Study (3) (0) | 2007/06/19 |
댓글을 달아 주세요