c++ singly linked list 단일 링크드 리스트 구현

* 본문은 <C++로 구현하는 자료구조와 알고리즘>(범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다.

 

1. 문자열 리스트를 가정할 경우

class StringNode { // 문자열 리스트의 노드
private:
    string elem;	// 원소값
    StringNode* next;	// 리스트의 다음 항목
    
    friend class StringLinkedList;
};

class StringLinkedList {
public:
    StringLinkedList(); // 빈 리스트 생성자
    ~StringLinkedList();
    bool empty() const;
    const string& front() const; // 맨 앞 원소를 얻음
    void addFront(const string& e);
    void removeFront();
private:
    StringNode* head;
}

*복습

- friend란?: 클래스의 프라이빗 멤버에 접근할 수 있게 하는 문법. 정보의 공유를 허용하기 위해 클래스들의 동작을 조정하는 이슈를 해결하기 위해 사용. 또 서로 다른 두 클래스가 밀접하게 관련 있는 경우에 이용한다. 단, 과도한 프렌드의 사용은 종종 클래스의 구조 설계를 나쁘게 한다. 프렌드 관계는 전이적(transitive)이지 않다. 만약 새 클래스 Tensor가 Matrix(Vector의 프렌드 클래스)의 프렌드로 정의되었다면 클래스 Vector에 명시적으로 정의하지 않는 한 Tensor는 Vector의 프렌드가 아니다.

StringLinkedList::StringLinkedList()
    : head(NULL) {}
    
StringLinkedList::~StringLinkedList()
    { while(!empty()) removeFront();}
  
  
bool StringLinkedList::empty() const // 빈 리스트인지 알아봄
    { return head == NULL; }
    
const string& StringLinkedList::front() const 
    { return head->elem; }
    
void StringLinkedList::addFront(const int & e) {
    StringNode* v = new StringNode;
    v->elem = e;
    v->next = head;
    head = v;
}

void StringLinkedList::removeFront() {
    StringNode* old = head;
    head = old->next;
    delete old;
}

소멸자는 리스트에 있는 원소들을 반복적으로 삭제한다.

*복습

- const를 반환한다는 것은?(front 메서드): 매개변수로 레퍼런스가 전달되지만, 함수는 그 값을 변경하지 못한다는 사실을 통보하는 것이다. 

- const 메서드란?(empty, front 메서드): 클래스 멤버 함수는 크게 두 부류로 나눌 수 있다. 접근 함수와 수정 함수. 둘은 객체 내용 변경 가능 여부로 갈린다. const 메서드는 접근 함수임을 알려준다, 이 함수를 통해 클래스 멤버 변수를 수정할 경우 에러를 생성하도록 컴파일러에게 지시한다.

* 대부분의 c++ 스타일 메뉴얼은 클래스 정의 내에 깔끔한 공용 인터페이스를 제공하기 위해 모든 멤버 함수들을 클래스 외부에 정의하는 것을 권고한다.

 

2. 일반적인 단일 링크드 리스트

template <typename E>
class SNode {
    private:
        E elem;
        SNode<E>* next;
        friend class SLinkedList<E>;
};

template <typename E>
class SLinkedList {
public:
    SLinkedList();
    ~SLinkedList();
    bool empty() const;
    const E& front const;
    void addfront(const E& e);
    void removeFront();
private:
    SNode<E>* head;
};

template <typename E>
SLinkedList<E>::SLinkedList()
    : head(NULL) { }

template <typename E>
bool SLinkedList<E>::empty() const
    { return head == NULL; }

template <typename E>
const E& SLinkedList<E>::front() const
    { return head->elem; }

template <typename E>
SLinkedList<E>::~SLinkedList()
    { while(!empty()) removeFront();}

template <typename E>
void SLinkedList<E>::addfront(const E& e) {
    SNode<E>* v = new SNode<E>;
    v->elem = e;
    v->next = head;
    head = v;
}

template <typename E>
void SLinkedList<E>::removeFront() {
    SNode<E>* old = head;
    head = old->next;
    delete old;
}