[자료구조] 연결 리스트 1 (개념, 체인 구현, 체인 조작 연산 1)

단순 연결 리스트

순차 표현(sequential)

- 연속된 원소들이 일정한 거리만큼 떨어져서 저장

- 임의 원소 접근, 스택이나 큐의 원소 삽입/삭제에 적합

- 순서 리스트에서 임의 원소의 삽입/삭제 비용 큼

ex) 오름차순 내림차순 배열의 경우 중간에 수를 삽입 또는 삭제하면 다른 원소들을 이동해야함

 

연결된 표현(linked)

- 각 원소들이 기억 장소 내의 어떤 곳에나 위치

- 노드: [데이타 | 링크(포인터)]

 

[데이타 | 링크(포인터)] → [데이타 | 링크(포인터)] → [데이타 | 링크(포인터)] → ... → [데이타 | 0]

 

노드 삽입

1. 현재 사용하고 있지 않은 노드 a 할당
2. 노드 a의 data 필드에 데이터 설정
3. 노드 a의 link 필드가 삽입하려는 위치 다음 노드를 가리키도록 설정
4. 삽입하려는 위치 이전 노드의 link 필드가 노드 a를 가리키도록 함

 

[데이타 | 링크] → [데이타 | 링크]

         [데이타 | 링크] ↗

 

[데이타 | 링크]           [데이타 | 링크]

            ↘  [데이타 | 링크] ↗

 

삽입할 때 리스트에 있는 다른 원소들의 이동이 불필요

link 필드를 위한 저장 공간이 추가로 사용

 

노드 삭제

1. 삭제하려는 위치 이전 노드의 링크가 다음 노드를 가르키도록 함
2. 삭제하려는 노드를 삭제

                  ↗  →  →  →  →  →  →  ↘

[데이타 | 링크]     [데이타 | 링크] → [데이타 | 링크]

 

C++에서의 체인 표현

설계 시도

class TreeLetterNode{
private:
    char data[3];
    ThreeLetterNode *link;
};

class NodeA{
private:
    int data1;
    char data2;
    float data3;
    NodeA *linka;
    NodeB *linkb;
};

class NodeB{
private:
    int data;
    NodeB *link;
};

노드 구조에 대한 예시

설계 시도 1

ThreeLeeterNode *first;                                      // 변수 선언
first → data, first → link                                       // first를 이용한 데이터 멤버 참조
first → data[0], first → data[1], first → data[2] // data의 요소 참조

→ data, link를 private로 선언해서 컴파일 오류

 

설계 시도 2

공용 멤버 함수를 만들어서 사용
→ 프로그램의 모든 함수가 위 멤버 함수들을 이용하여 데이터 멤버에 접근할 수 있는 문제

리스트 조작 연산을 수행하는 함수에 대해서만 TreeLatterNode의 데이터 멤버에 접근할 수 있도록 허용

 

설계 시도 3

전체 체인에 대응하는 클래스 ThreeLetterChain 구현
→ 삽입, 삭제와 같은 리스트 조작 연산 수행하는 멤버 함수 포함

TreeLatterNode와 TreeLatterChain을 조합하여 사용

TreeLatterChain을 TreeLatterNode 객체로 구성
→ TreeLatterChain HAS-A TreeLatterNode

 

체인 클래스 설계

Type A 클래스가 Type B 클래스를 데이터 멤버로 가짐

타입 A의 객체가 일정한 수의 타입 B의 객체를 포함하고 있는 경우

두 클래스 사이의 관계

ThreeLetterChain에 포함될 ThreeLetterNode의 수를 미리 아는 것은 불가능

 

클래스 ThreeLetterChain은 리스트의 첫 번째 노드를 지시하는 접근 포인터, first만 포함하도록 정의

 

코드 1

class TreeLetterChain; // 노드 클래스에서 사용하므로 미리 선언

class ThreeLetterNode {
friend class ThreeLetterChain;
private:
    char data[3];
    ThreeLetterNode *link;
};

class ThreeLetterChain {
public:
    // 리스트 조작 연산
    //
    //
private:
    ThreeLetterNode *first;
};

 

ThreeLetterChain을 ThreeLetterNode의 friend로 선언

두 클래스 사이의 관계

ThreeLetterChain과 ThreeLetterNode의 멤버 함수들만 ThreeLetterNode의 private 데이터 멤버에 접근 가능

 

코드 2

class ThreeLetterChain {
public:
    // 리스트 조작 연산
    //
    //
private:
    class ThreeLetterNode { // 중첩 클래스
    private:
        char data[3];
        ThreeLetterNode *link;
    };
    ThreeLetterNode *first;
};

중첩 클래스

- 하나의 클래스가 다른 클래스 안에서 정의

- ThreeLetterNode 객체가 클래스 ThreeLetterChain의 외부로부터 접근될 수 없도록 보장

- ThreeLetterNode의 데이터 멤버들은 public

 

체인 조작 연산

class ChainNode {
friend class Chain;
public:
    ChainNode(int element = 0, ChainNode *next = 0)
    {
        data = element;
        link = next;
    }
private:
    int data;
    ChainNode *link;
};

체인의 첫 번째 노드를 지시하고 있는 접근 포인터 first는 Chain의 전용 데이터 멤버

체인 조작 연산을 위한 함수는 Chain 클래스의 public 멤버

 

체인 조작 연산 예시

2-노드 리스트 생성

void Chain::Create2()
{
    // 두 번째 노드를 생성하고 초기화
    ChainNode* second = new ChainNode(20, 0);
    
    // 첫 번째 노드를 생성하고 초기화
    first = new ChainNode(10, second);
}

first → [10 | -]->[20 | 0]

 

노드 삽입

void Chain::Instrt50(ChainNode *x)
{ // x가 가리키는 노드 다음에 삽입
    if (first)
        // x다음에 삽입
        x->link = new ChainNode(50, x->link);
    else
        // 공백 리스트에 삽입
        first = mew ChainNode(50);
}

 

노드 삭제

void Chain::Delete(ChainNode *x, ChainNode *y)
{ // y는 삭제할 노드의 이전 노드를 가리
    if (x == first)
        first = first->link;
    else
        y->link = x->link;
    delete x;
}

 

템플릿 클래스 체인

template <class T>
class Chain; // 전방 선언

template <class T>
class ChainNode
{
friend class Chain<T>;
private:
    T data;
    ChainNode<T> *link;
};

template <class T>
class Chain
{
public:
    Chain() { first = 0; }; 
    // first를 0으로 초기화하는 생성자
    // 체인 조작 연산들
    //
    //
private:
    ChainNode<T> *first;
};