리스트란?
리스트(list) 또는 선형 리스트(linear list)는 자료를 정리하는 방법 중의 하나이다.
리스트에는 보통 항목들이 차례대로 정리되어 있다, 리스트의 항목들은 순서 또는 위치를 가진다. 리스트는 집합과는 다르다. 집합은 각 항목 간에 순서의 개념이 없지만 리스트에 들어 있는 항목들 사이에는 순서가 있다.
리스트는 스택, 큐, 덱과 같은 선형 자료구조이다.
이 때 선형이란 항목들이 일렬로 순서대로 들어 있는 것을 의미한다. 리스트와 이들 자료구조의 차이는 항목에 대한 접근 방법이다.
스택, 큐, 덱에서 자료의 접근은 전단(front)와 후단(rear)에 제한 되어 있다.
→ 세로운 항목에 대한 삽입이나 삭제 연산이 맨 앞이나 맨 뒤로 제한 되어있다.
→ 중간에 새로운 객체를 삽입하거나 삭제할 수 없다.
리스트는 위의 제한이 없다. 즉, 임의의 위치에 있는 항목에 대한 연산을 허용한다는 것이다. → 선형 자료구조들 중에서 가장 많이 활용되는 이유
리스트의 추상 자료형
리스트에는 다음과 같은 연산들이 필요할 것이다.
- 리스트의 어떤 위치에 새로운 요소를 삽입한다.
- 리스트의 어떤 위치에 있는 요소를 삭제한다.
- 리스트의 어떤 위치에 있는 요소를 반환한다.
- 리스트가 비어 있는지를 검사한다.
- 리스트가 가득 차있는지를 검사한다.
- 리스트에 어떤 요소가 있는지를 검사한다.
- 리스트의 어떤위치에 있는 요소를 새로운 요소로 대치한다.
- 리스트 안의 요소의 개수를 센다.
- 리스트 안의 모든 요소를 출력한다.
이 외에도 많은 추가적인 연산을 만들 수 있다.
| 객체 | 임의의 접근 방법을 제공하는 같은 타입 요소들의 순서 있는 모임 |
|---|---|
| 연산 | insert(pos, item): 리스트의 pos 위치에 새로운 요소 item을 삽입한다. |
| delete(pos): 리스트의 pos 위치에 있는 요소를 삭제한다. | |
| getEntry(pos): 리스트의 pos 위치에 있는 요소를 반환한다. | |
| isEmpty(): 리스트가 비어 있는지를 검사한다. | |
| isFull(): 리스트가 가득 차 있는지를 검사한다. | |
| find(item): 리스트에 요소 item이 있는지를 살핀다. | |
| replace(pos item): 리스트의 pos 위치에 있는 요소를 새로운 요소 item으로 교체한다. | |
| size(): 리스트 안의 요소의 개수를 반환한다. | |
| display(): 리스트 안의 모든 요소들을 출력한다. |
배열로 구현한 리스트
1. 삽입 연산
2. 삭제 연산
연결 리스트로 구현된 리스트
1. 삽입 연산
2. 삭제 연산
※주의
노드를 삭제하기 위해서는 삭제할 노드가 아니라 삭제할 노드의 선행 노드를 알아야 한다.
시작 노드 표현 방법: 헤드 포인터와 헤드 노드
배열로 리스트를 구현하는 것과 달리 연결 리스트에서는 시작 노드의 주소만을 관리한다.
시작 노드의 주소(헤드 포인터)를 멤버 변수로 선언하는 방법(헤드 포인터 방식)이 아닌 다름 방법으로 표현할 수 있다.
class LinkedList { // 단순 연결 리스트 클래스
Node org; // 헤드 노드 org를 멤버로 가지는 경우
... // 실제 헤드 포인터는 org.link가 된다.
}이 방법은 시작 노드를 가리킬 포인터 변수가 아니라 노드 객체를 리스트의 데이터 멤버로 갖는다. 이와 같은 노드를 헤드 노드(Head Node)라 부른다.
헤드노드는 의미 있는 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 리스트 클래스에 하나의 노드 객체를 선언하여 사용하는 것이다. 실질적인 연결 리스트의 시작 노드는 헤드 노드의 링크 필드가 가리키고 있다.
단순 연결 리스트를 통한 구현
Node.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
inline void error( char* str ) {
fprintf(stderr, "%s\n", str);
exit(1);
};
class Node
{
Node* link;
int data;
public:
Node( int val=0) : data(val), link(NULL) { }
Node* getLink() { return link; }
void setLink(Node* next) { link = next; }
void display() { printf(" <%2d>", data); }
bool hasData(int val) { return data == val; }
void insertNext( Node *n ) {
if( n != NULL ) {
n->link = link;
link = n;
}
}
Node* removeNext( ) {
Node* removed = link;
if( removed != NULL )
link = removed->link;
return removed;
}
};LinkedList.h
#pragma once
#include "Node.h"
class LinkedList
{
Node org; // 헤드 노드 (헤드 포인터가 아님)
public:
LinkedList(): org(0) { }
~LinkedList() { clear(); }
void clear() { while(!isEmpty()) delete remove(0); }
Node* getHead() { return org.getLink(); }
bool isEmpty( ) { return getHead()==NULL; }
Node* getEntry(int pos) {
Node* n = &org;
for(int i=-1 ; i<pos ; i++, n=n->getLink())
if( n == NULL ) break;
return n;
}
void insert(int pos, Node *n) {
Node* prev = getEntry(pos-1);
if( prev != NULL )
prev->insertNext( n );
}
Node* remove(int pos) {
Node* prev = getEntry(pos-1);
return prev->removeNext();
}
Node* find(int val) {
for( Node *p = getHead() ; p != NULL ; p=p->getLink() )
if( p->hasData( val ) ) return p;
return NULL;
}
void replace(int pos, Node *n) {
Node* prev = getEntry(pos-1);
if( prev != NULL ) {
delete prev->removeNext( );
prev->insertNext( n );
}
}
int size( ){
int count = 0;
for( Node *p = getHead() ; p != NULL ; p=p->getLink() )
count++;
return count;
}
void display( ) {
printf( "[단순연결리스트 항목 수 = %2d] : ", size());
for( Node *p = getHead() ; p != NULL ; p=p->getLink() )
p->display();
printf( "\n");
}
void reverse() {
for (Node *p = getHead(); p != NULL; p = p->getLink())
{
int cnt = 0;
for (int i = 0; i < size(); i++) {
Node *p = remove(size() - 1);
insert(cnt++, p);
}
}
}
void Arrageinsert(Node *n) {
Node *low = 0;
Node *high = 0;
Node *std = getEntry(0);
if (std != NULL)
{
if (n >= low)
low = n;
else if (n <= high)
high = n;
if (n <= low)
{
n->getLink = high->getLink;
high->getLink = n;
}
else if (high <= n)
{
std->insertNext(n);
}
}
}
};다양한 형태의 연결 리스트
1. 원형 연결 리스트(circular linked list)
원형 연결 리스트는 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트를 말한다. → 마지막 노드의 링크가 NULL이 아닌 첫 번째 노드의 주소
원형 연결 리스트는 한 노드에서 다른 모든 노드로의 접근이 가능하다는 점이 있다.
2. 이중 연결 리스트(double linked list)
단순 연결 리스트는 어떤 노드에서 후속 노드를 찾기는 쉽지만 선행 노드를 찾기는 매우 어려운 구조이다. 즉, 헤드 포인터부터 시작해서 리스트 항목에 대한 탐색이 필요하다.
이중 연결 리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두개의 링크를 가지는 리스트이다.
링크가 양방향이므로 양방향 검색이 가능해진다. 단점으로는 공간을 많이 차지하고 코드가 복잡해진다는 것이 있다.
