[개탱][C++][Collection (Container) 객체][Single Linked_List]

Collection (Container) 객체

*Array, Stack, Queue, LinkedList, ArrayList, vector, HashMap

(모두 모양, 효율성, 사용 목적&방법이 모두 다르다)

이전에 한번 다루었지만 한번더 복습겸 정리입니다

이전글 :: http://gaetaeng.tistory.com/10 (C의 구조체를 활용한 Linked_List)

이번에 다룰내용은 LinkedList 와 관련해서 다룰 것인데,

LinekdList는 "Array의 문제점을 개선해서 만들어진 Collection 이다." 라고 말할수 있다.

( Array의 단점 )

 - 크기 고정 ( Overflow가 생기거나 공간낭비가 생길 수 있다. )

 - 삽입/삭제 시 시간이 오래걸린다.

예제로는 이전에 C의 구조체를 이용하여 짯으니 이번에는 (C Linked_List 부터 보고 이해하고 오셔야합니다 !)

C++의 클래스를 이용하여 구현을 해보도록 하겠습니다.

먼저 우리는

int main()
{
    LinkedList li;
    li.addFirst(30);
    li.addFirst(20);
    li.addFirst(10);
}

와 같이 사용을 하기 위하여 LinkedList 라는 타입을 짜야 할 것이며,

그 클래스 내부에 addFirst라는 MemberFunction이 존재해야 할 것입니다.

( Class 관련링크 ) ( 이해안되면 댓글을 달아주세요!)

http://blog.naver.com/nuckly/221100423803

그렇기에 

class LinkedList {
public:
    LinkedList();
    void addFirst(int x) {
    }
};

와 같이 클래스를 명시적으로 선언을 해줍니다.

그 뒤 객체지향적으로 노드 하나하나에 대한 클래스에 대하여 생각을 해봅시다.

Node하나에 필요한 것이 안에 값을 넣을 data가 필요할것이며 

다음을 가리킬 Pointer가 필요할 것입니다. 그렇기에

class ListNode {//Node 하나에 대한 클래스
private: // 생략해도 default 로 private임.
    int data;
    ListNode* pNext;
};
 

를 생성하여 줍니다. 또한 처음 Node가 만들어지면서 처음 초기값을 가지며, 다음위치를 가질수 있게 만들어주기위해

class ListNode { // Node 하나에 대한 클래스
private: // 생략해도 default 로 private임.
    int data;
    ListNode* pNext;
    ListNode(int x); // 값만 넣어주는 생성자
    ListNode(int x, ListNode* next); 
    // 다음을 가리키는 곳까지 알려주는 생성자
};
 

와 같이 만들어줍니다. 

그후 LinkedList의 클래스의 addFirst를 구현하여 보면

void LinkedList::addFirst(int x) {
    ListNode* pNode = new ListNode(x, pHead);
    pHead = pNode;
}
 

다음과 같이 만들어 진다(여기서 맨 처음에 넣는다면 pHead값이 NULL이기 때문에 알아서 다음이 NULL이 되며

그다음부터는 pHead에는 맨처음의 주소가 있으므로 그것을 pNode에 넣음으로서 다음주소로 지정되게 한다)

그후 우리는 li라는 List를 출력하고싶은데 이전처럼

cout << li ; 이런식으로 하고싶다 그렇기때문에

우리는 operator overloading 을 이용하여

 ostream& operator<<(ostream& outs, LinkedList &l) {
    if (l.pHead == NULL) {//만약 pHead의 값이 NULL 이라면
        outs << " { } " << endl; // Node가 하나도 없다는 뜻이기때문에
        return outs; // 틀만 출력후 종료
    }
    outs << " { ";
    ListNode *pNode = l.pHead;
    while(pNode != NULL) {
        outs << pNode->getData() << " ";
        pNode = pNode->getpNext();
    }
    outs << "} " << endl;
}

이와 같이 짜게된다.

이다음 이제 마지막에 추가하는 addLast를 만들어줘보자

void LinkedList::addLast(int x) {
    ListNode *pNode = new ListNode(x);
    if(pHead == NULL) { // 현 List의 첫 노드가 NULL이라면
        pHead = pNode; // pHead를 Node로 옮겨주고
        return ; // 종료
    }//아니라면
    ListNode * pTraverse = pHead; // List사이를 돌아다닐 포인터 Node Pointer를 하나 생성후 처음위치를 가리키게 한다.
    while(pTraverse->getpNext() != NULL){ // 그 노드의 다음노드가 NULL이 아니라면
        pTraverse = pTraverse->getpNext(); // 계속 이동 해서 NULL이 되게끔 만들어준뒤
    }//종료가 된다면 이제 마지막 노드라는 뜻이므로
    pTraverse->SetpNext(pNode); // 그 노드의 다음에 pNode를 넣어주게되면 
    //마지막 노드에 pNode를 추가한것과 같은 상황이 된다.
}
 

현재까지의 노드들로

#include <iostream>
 
using namespace std;
class ListNode { // Node 하나에 대한 클래스
private: // 생략해도 default 로 private임.
    int data;
    ListNode* pNext;
public:
    ListNode(int x); // 값만 넣어주는 생성자
    ListNode(int x, ListNode* next); 
    int getData() {
        return this->data;
    }
    ListNode* getpNext()
    {
        return this->pNext;
    }
    void SetpNext(ListNode* pNode)
    {
        this->pNext = pNode;
    }
    // 다음을 가리키는 곳까지 알려주는 생성자
};
ListNode::ListNode(int x) { // Node 초기화
    data = x;
    pNext = NULL; // 연결 시켜주기전에는 NULL 로 초기화를 시켜놓는다.
}
ListNode::ListNode(int x, ListNode* next) { // Node 초기화
    data = x;
    pNext = next; // 다음의 장소를 이제는 알고있기때문에 그곳을 가리키게 한다.
}
 
 
class LinkedList { // List에 대한 클래스
    ListNode* pHead; // Node들의 맨 처음을 가리키는 포인터
public:
    LinkedList();
    void addFirst(int x);
    void addLast(int x);
    friend ostream& operator<<(ostream& outs, LinkedList &l);
};
LinkedList::LinkedList() {
    pHead = NULL;
}
void LinkedList::addFirst(int x) {
    ListNode* pNode = new ListNode(x, pHead); 
    //(여기서 맨 처음에 넣는다면 pHead값이 NULL이기 때문에 알아서 다음이 NULL이 되며
    //그다음부터는 pHead에는 맨처음의 주소가 있으므로 그것을 pNode에 넣음으로서 다음주소로 지정되게 한다)
    pHead = pNode;
 
}
 
void LinkedList::addLast(int x) {
    ListNode *pNode = new ListNode(x);
    if(pHead == NULL) { // 현 List의 첫 노드가 NULL이라면
        pHead = pNode; // pHead를 Node로 옮겨주고
        return ; // 종료
    }//아니라면
    ListNode * pTraverse = pHead; // List사이를 돌아다닐 포인터 Node Pointer를 하나 생성후 처음위치를 가리키게 한다.
    while(pTraverse->getpNext() != NULL){ // 그 노드의 다음노드가 NULL이 아니라면
        pTraverse = pTraverse->getpNext(); // 계속 이동 해서 NULL이 되게끔 만들어준뒤
    }//종료가 된다면 이제 마지막 노드라는 뜻이므로
    pTraverse->SetpNext(pNode); // 그 노드의 다음에 pNode를 넣어주게되면 
    //마지막 노드에 pNode를 추가한것과 같은 상황이 된다.
}
 
ostream& operator<<(ostream& outs, LinkedList &l) {
    if (l.pHead == NULL) {//만약 pHead의 값이 NULL 이라면
        outs << " { } " << endl; // Node가 하나도 없다는 뜻이기때문에
        return outs; // 틀만 출력후 종료
    }
    outs << " { ";
    ListNode *pNode = l.pHead;
    while(pNode != NULL) { // 현재 노드가 NULL이 아니라면 값이 존재한다는 것이니
        outs << pNode->getData() << " "; // 출력
        pNode = pNode->getpNext(); // 다음노드로 이동
        //만약 다음노드가 NULL이라면 while의 조건식에 들어가서 NULL확인후 종료
    }
    outs << "} " << endl;
 
 
}
int main()
{
    LinkedList li;
    li.addFirst(30);
    cout << li;
    li.addFirst(20);
    cout << li;
    li.addFirst(10);
    cout << li;
    li.addLast(50);
    cout << li;
    li.addLast(70);
    cout << li;
    cout << li;
}

현재까지의 결과로 출력을 해보면

이렇게 정상적으로 나오게 된다

그 뒤 

    int iSize = li.size();
    cout << iSize << endl;

로 List의 사이즈를 확인하고 싶을때는

List 클래스에 

int _Size; 

를 추가해주고

addFirst  addLast에 

_Size++;

 을 해줌으로서 그 값을 하나씩 증가시키고 간단하게

LinkedList 의 클래스에  MemberFunction 으로

int size(){
        return _Size;
}

와 같이 추가를 해준다.

그후 isEmpty ( 비어있는지 확인 ) 등등 여러함수를 만들어봅시다.

#include <iostream>
 
using namespace std;
 
typedef void* POSITION; 
// void* 를 사용하면 아무타입이나 가리키게 할수있음.
 
 
class ListNode { // Node 하나에 대한 클래스
private: // 생략해도 default 로 private임.
    int data;
    ListNode* pNext;
public:
    ListNode(int x); // 값만 넣어주는 생성자
    ListNode(int x, ListNode* next); 
    int getData() {
        return this->data;
    }
    ListNode* getpNext()
    {
        return this->pNext;
    }
    void SetpNext(ListNode* pNode)
    {
        this->pNext = pNode;
    }
    // 다음을 가리키는 곳까지 알려주는 생성자
};
ListNode::ListNode(int x) { // Node 초기화
    data = x;
    pNext = NULL; // 연결 시켜주기전에는 NULL 로 초기화를 시켜놓는다.
}
ListNode::ListNode(int x, ListNode* next) { // Node 초기화
    data = x;
    pNext = next; // 다음의 장소를 이제는 알고있기때문에 그곳을 가리키게 한다.
}
 
 
class LinkedList { // List에 대한 클래스
    ListNode* pHead; // Node들의 맨 처음을 가리키는 포인터
    int _Size;
public:
    LinkedList();
    void addFirst(int x);
    void addLast(int x);
    int size(){ // 사이즈 확인
        return _Size;
    }
    int isEmpty(){ // 비어있는지 확인 ( 비었으면 1 차있으면 0 을 리턴)
        if(_Size == 0) return 1;
        return 0;
    }
    //POSITION은 위에 typedef로 void* 가리키게 해놓았다.
    //void* 타입은 http://blog.naver.com/nuckly/221142498384
    POSITION getHeadPosition() { // 맨처음의 포지션을 받아오는 함수
        return (POSITION)pHead;
    }
    int getNext(POSITION &pos) { // pNext를 받아오는 함수(private이라서 밖에서 접근 불가능)
        ListNode *pNode = (ListNode *)pos;
        int value = pNode->getData();
        pNode = pNode->getpNext();
        pos = (POSITION)pNode;
        return value;
    }
 
    friend ostream& operator<<(ostream& outs, LinkedList &l);
};
LinkedList::LinkedList() {
    pHead = NULL;
    _Size = 0;
}
void LinkedList::addFirst(int x) {
    _Size++;
    ListNode* pNode = new ListNode(x, pHead); 
    //(여기서 맨 처음에 넣는다면 pHead값이 NULL이기 때문에 알아서 다음이 NULL이 되며
    //그다음부터는 pHead에는 맨처음의 주소가 있으므로 그것을 pNode에 넣음으로서 다음주소로 지정되게 한다)
    pHead = pNode;
 
}
 
void LinkedList::addLast(int x) {
    _Size++;
    ListNode *pNode = new ListNode(x);
    if(pHead == NULL) { // 현 List의 첫 노드가 NULL이라면
        pHead = pNode; // pHead를 Node로 옮겨주고
        return ; // 종료
    }//아니라면
    ListNode * pTraverse = pHead; // List사이를 돌아다닐 포인터 Node Pointer를 하나 생성후 처음위치를 가리키게 한다.
    while(pTraverse->getpNext() != NULL){ // 그 노드의 다음노드가 NULL이 아니라면
        pTraverse = pTraverse->getpNext(); // 계속 이동 해서 NULL이 되게끔 만들어준뒤
    }//종료가 된다면 이제 마지막 노드라는 뜻이므로
    pTraverse->SetpNext(pNode); // 그 노드의 다음에 pNode를 넣어주게되면 
    //마지막 노드에 pNode를 추가한것과 같은 상황이 된다.
}
 
ostream& operator<<(ostream& outs, LinkedList &l) {
    if (l.pHead == NULL) {//만약 pHead의 값이 NULL 이라면
        outs << " { } " << endl; // Node가 하나도 없다는 뜻이기때문에
        return outs; // 틀만 출력후 종료
    }
    outs << " { ";
    ListNode *pNode = l.pHead;
    while(pNode != NULL) { // 현재 노드가 NULL이 아니라면 값이 존재한다는 것이니
        outs << pNode->getData() << " "; // 출력
        pNode = pNode->getpNext(); // 다음노드로 이동
        //만약 다음노드가 NULL이라면 while의 조건식에 들어가서 NULL확인후 종료
    }
    outs << "} " << endl;
 
 
}
int main()
{
    LinkedList li;
    li.addFirst(30);
    cout << li;
    li.addFirst(20);
    cout << li;
    li.addFirst(10);
    cout << li;
    li.addLast(50);
    cout << li;
    li.addLast(70);
    cout << li;
 
    int iSize = li.size();
    cout << iSize << endl;
 
    if(li.isEmpty()) {
        cout << "Yes" << endl;
    }else {
        cout << "NO" << endl;
    }
}
 

자세한건 주석으로 달아놓았습니다! 궁금하신 분들은글로 달아주시면 답변드리겠습니다!