5.2 연결리스트
연결리스트는 노드의 선형 집합입니다. 노드란 데이터와 링크의 조합으로 하나의 데이터를 보관하는 작은 저장소입니다. 그리고 링크는 노드의 위치 정보입니다.
[그림 5.1] 연결리스트
연결리스트는 노드에 링크가 하나만 있는 단일(단순) 연결리스트와 링크가 두 개 있는 이중 연결리스트로 구분할 수 있습니다.
이 책에서는 노드에 이전 노드의 위치 정보를 가르키는 링크와 다음 노드의 위치 정보를 가르키는 링크를 갖고 있는 이중 연결리스트를 만들고 사용하는 방법을 소개할 것입니다.
특히 연결리스트를 생성할 때 연결리스트의 맨 앞과 맨 뒤에 더미 노드를 생성하여 자료를 보관하는 노드들을 이들 사이에 배치할게요.
5.2.1 연결리스트 설계
동적 배열처럼 연결리스트도 동적으로 생성한 개체는 형식에 관계없이 보관할 수 있게 정의할게요. 사용하기 편리하게 void * 형식을 Element 형식으로 타입 재지정할게요.
typedef void * Element;
연결리스트는 노드의 선형 집합입니다. 노드는 링크와 데이터의 조합으로 여기에서는 두 개의 링크를 갖는 노드를 정의할 것입니다.
typedef struct _Node Node;
typedef Node *Link;
struct _Node
{
Link next;
Link prev;
Element data;
};
연결리스트 구조체에는 맨 앞에 있는 더미 노드의 위치 정보인 head와 맨 뒤에 있는 더미 노드의 위치 정보인 tail과 보관한 자료 개수를 멤버로 구성할게요.
typedef struct _LinkedList LinkedList;
struct _LinkedList
{
Link head;
Link tail;
int usage;
};
연결리스트를 동적으로 생성하는 함수와 소멸하는 함수를 선언합시다.
LinkedList *New_LinkedList();
void Delete_LinkedList(LinkedList *linkedlist);
연결리스트에 순차적으로 보관하기 위한 함수를 제공합시다.
void LinkedList_PushBack(LinkedList *linkedlist,Element data);
원하는 노드 앞에 보관하는 함수도 제공합시다. 여기에서는 노드의 위치 정보를 Link로 타입 재지정한 것을 기억하세요.
void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data);
맨 앞에 보관한 자료가 있는 노드의 위치 정보를 구하는 함수와 맨 뒤에 보관한 자료가 있는 노드의 다음 노드 위치를 구하는 함수를 제공합시다.
Link LinkedList_Begin(LinkedList *linkedlist);
Link LinkedList_End(LinkedList *linkedlist);
특정 위치의 노드를 제거하는 함수도 제공합시다.
void LinkedList_Erase(LinkedList *linkedlist,Link pos);
연결리스트는 배열과 다르게 자료를 저장하는 저장소가 연속적인 메모리에 할당하는 것이 아니라 독립적인 노드에 보관하고 단지 노드의 링크가 다른 노드의 위치를 알고 있는 것입니다. 따라서 인덱스 연산으로 보관한 자료를 변경하거나 얻어오는 기능은 제공하지 않을게요.
또한 인덱스로 배열을 사용하기 전에 디폴트 값으로 최대 보관할 자료 개수만큼 설정하는 함수도 제공하는것이 별다른 의미가 없어 제공하지 않기로 합시다.
//LinkedList.h
#pragma once
typedef void * Element;
typedef struct _Node Node;
typedef Node *Link;
struct _Node
{
Link next;
Link prev;
Element data;
};
typedef struct _LinkedList LinkedList;
struct _LinkedList
{
Link head;
Link tail;
int usage;
};
LinkedList *New_LinkedList();
void Delete_LinkedList(LinkedList *linkedlist);
void LinkedList_PushBack(LinkedList *linkedlist,Element data);
void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data);
Link LinkedList_Begin(LinkedList *linkedlist);
Link LinkedList_End(LinkedList *linkedlist);
void LinkedList_Erase(LinkedList *linkedlist,Link pos);
관련 게시글
[디딤돌 자료구조와 알고리즘] 5. 선형 자료구조 - 개요
[디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.2 연결리스트 구현
[디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.3 연결리스트 테스트
C언어 예제
단일 연결리스트 - 역순 보관(가장 최근에 보관한 데이터가 맨 앞), C언어 소스
원형 연결리스트 - 단일 연결리스트, 순차 보관, C언어 소스
이중 연결리스트 - 역순 보관(가장 최근에 보관한 데이터가 맨 앞), C언어 소스
이중 연결리스트 - 동적 생성한 데이터 보관, C언어 소스
디딤돌 자료구조와 알고리즘 with C++
3.2 연결리스트와 list [디딤돌 자료구조와 알고리즘 with C++]
3.2.1 단순 연결리스트 만들기 [디딤돌 자료구조와 알고리즘 with C++]
3.2.2 이중 연결리스트 만들기 [디딤돌 자료구조와 알고리즘 with C++]
5. list 만들기 [디딤돌 자료구조와 알고리즘 with C++]
자료구조와 STL
'언어 자료구조 알고리즘 > [C]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| [디딤돌 자료구조와 알고리즘] 5.3.2 큐 구현 , 5.3.3 큐 테스트 (0) | 2016.05.23 |
|---|---|
| [디딤돌 자료구조와 알고리즘] 5.3.1 큐(QUEUE) 설계 (0) | 2016.05.23 |
| [디딤돌 자료구조와 알고리즘] 5.3 큐(QUEUE) (0) | 2016.05.23 |
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.3 연결리스트 테스트 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.2 연결리스트 구현 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.3 동적 배열 테스트 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.2 동적 배열 구현 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.1 동적 배열 설계 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5. 선형 자료구조 - 개요 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 4.3.2 병합 정렬 알고리즘 구현 (0) | 2016.04.10 |