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

http://gaetaeng.tistory.com/39

[Collection (Container) 객체][Single Linked_List]

Double Linked List

 - Single Linked List 의 단점을 보완하기 위해서 만들어짐.

Single Linked 의 단점

 - 순방향으로만 탐색이 가능. (  제일 앞에서부터 1번 2번 3번... 이런식으로 하나하나 확인을 해야함 )

서로 양방향을 탐색을 가능하게 해줌으로서 앞에서 부터 뒤로 순차적으로만 이동이 아닌

뒤로 가다가도 앞으로 가고 앞으로 가다가도 뒤로가는 행위가 가능해진다.

노드가 여러개인 Double Linekd List 을 자전거 체인과 비슷하다 하여 Chain 이라고도 부른다.

기본적인 코드들은 이전 Single Linekd List에서 다 짜봤으니 생략하고 바로 코드예제로 가겠습니다.

먼저 Double Linked List에서 Single Linked List와 다른점은 기본적으로 생성자에서 차이가 있습니다.

[주석]

ListNode:: ListNode(int x) {
    iValue = x;
    pPrev = this;
    pNext = this;
    // Single Linked List 에서는 pNext 에 NULL 을 넣어주었지만
    // Double Linked List 에서는 위 이미지와 같이  끝까지 간뒤에 다시 처음으로
    // 되돌아 오는 구조이기 때문에 일단 노드들을 만들 때 자기자신 혼자만 있다고 생각하고
    // 자신의 이전(pPrev)과 다음(pNext)이 자신을 가리키게끔 만들어둔다.
}
 

 

또한 Double Linked List 에서는 이전과 다음에 대한 이동(탐색)이 가능하기 때문에 

특정부분에 대한 삽입(insert)[특정 노드의 이전에 삽입]가 가능해집니다.

먼저 각 Node 개인에 의한 insert를 짜보겠습니다.

[주석]

void insert(ListNode* pNode) { 
        // pNode자리의 이전에 this(자기자신) Node를 끼워넣는 함수 //
        pNext = pNode;
        //현재 노드의 다음 노드를 pNode(기준 노드)
        pPrev = pNode->getpPrev();
        //현재 노드의 이전 노드를 pNode(기준 노드)의 이전(pPrev)노드로 설정해줌으로서
        // 현재 노드가 pNode(기준노드)의 왼쪽에 들어가게 됩니다.
 
 
 
        //이걸로 끝이 아닌 이제 this(자기자신) 양옆의
        // 노드들이 자신을 가리키게 해야하므로
        pNode->getpPrev()->setpNext(this);
        // pNode의 이전 Node의 다음 Node를 this(자기자신) 노드를 
        // 가리키게 한다.
        pNode->setpPrev(this);
        // pNode의 이전 Node를 this(자기자신) 노드를 가리키게 한다.
    }
 

이번에는 Double Linked List의 특성에 의하여 또 다른 삽입(append)[특정 노드의 다음에 삽입] 역시 가능해 집니다.

또한 특정 부분에 대한 삽입이 가능해진다면 이번에는

특정 노드에 대한 삭제(remove)역시 가능해집니다.

[주석]

void remove() {
        //현재 노드를 삭제하는 함수.
        pPrev->pNext = pNext; 
        //this의 이전 노드의 다음노드를 this의 다음노드로 설정해준다.
        pNext->pPrev = pPrev;
        //this의 다음 노드의 이전노드를 this의 이전노드로 설정.
        delete this;
        // 그 후 자기자신 삭제.
    }
 

.지금까지는 각 개개인의 Node에 대한 코드를 짯었는데

이번에는 전체 List에 대한 함수들을 짜보도록 하겠습니다..

먼저 List의 마지막에 노드를 삽입시켜주는 addLast

[주석]

void LinkedList::addLast(int x) {
    //리스트의 마지막에 노드하나 삽입.
    ListNode* pNewNode = new ListNode(x);
    if(pHead == NULL){
        // 리스트가 비어있을때에는 pHead가 NULL이기 때문에
        pHead = pNewNode; // 바로 직접적으로 가리키게 하고 
        return;//끝
    }
    pNewNode->insert(pHead);
    //pHead가 List의 처음을 가리키고 있기때문에
    //처음의 이전 = 마지막 이기때문에
    //insert를 통하여 pHead의 이전에 넣어주면 마지막에 넣는걸로 된다.
}
 

.

또한 마지막에 넣는다면 이번에는 처음에 넣는 addFirst

[주석]

void LinkedList::addFirst(int x){
    addLast(x); // 추가를 원하는 노드를 마지막에 넣어놓고
    pHead = pHead->getpPrev();
    //처음을 Head의 이전을 가리키게 해주면
    // 마지막이 처음이 되면서 처음을 가리키는것 처럼 된다.
}
 

나머지 isEmpty, Operator Overloading 등등 같은 경우에는 이전에 계속 짜 보았기때문에

전체 예시 코드만 올리도록 하겠습니다. 자세한건 주석처리 했습니다 !!

#include <iostream>
 
using namespace std;
 
class ListNode{
private:
    ListNode* pPrev; 
    // 노드의 이전에 있는 노드를 가리킬 포인터 
    ListNode* pNext; 
    // 노드의 다음에 있는 노드를 가리킬 포인터
    int iValue;
    // 노드의 값을 저장할 정수형 변수
public:
    ListNode();
    ListNode(int x);
 
    int getiValue() { return iValue; }
    void SetiValue(int x) { iValue = x; }
    ListNode* getpNext() { return pNext; }
    void setpNext(ListNode* p) { pNext = p; }
    ListNode* getpPrev() { return pPrev; }
    void setpPrev(ListNode* p) { pPrev = p; }
 
    void insert(ListNode* pNode) { 
        // pNode자리의 이전에 this(자기자신) Node를 끼워넣는 함수 //
        pNext = pNode;
        //현재 노드의 다음 노드를 pNode(기준 노드)
        pPrev = pNode->getpPrev();
        //현재 노드의 이전 노드를 pNode(기준 노드)의 이전(pPrev)노드로 설정해줌으로서
        // 현재 노드가 pNode(기준노드)의 왼쪽에 들어가게 됩니다.
 
 
 
        //이걸로 끝이 아닌 이제 this(자기자신) 양옆의
        // 노드들이 자신을 가리키게 해야하므로
        pNode->getpPrev()->setpNext(this);
        // pNode의 이전 Node의 다음 Node를 this(자기자신) 노드를 
        // 가리키게 한다.
        pNode->setpPrev(this);
        // pNode의 이전 Node를 this(자기자신) 노드를 가리키게 한다.
    }
 
    void append(ListNode* pNode) {
        pNext = pNode->getpNext();
        //현재노드의 다음노드를  기준노드의 다음노드로
        pPrev = pNode;
        //현재노드의 이전노드를 기준노드로
 
        pNode->getpNext()->setpPrev(this);
        //기준노드의 다음노드의 이전노드보고 현재노드를 가리키게 한다.
        pNode->setpNext(this);
        // 기준노드의 다음노드보고 현재노드를 가리키게 한다.
    }
 
    void remove() {
        //현재 노드를 삭제하는 함수.
        pPrev->pNext = pNext; 
        //this의 이전 노드의 다음노드를 this의 다음노드로 설정해준다.
        pNext->pPrev = pPrev;
        //this의 다음 노드의 이전노드를 this의 이전노드로 설정.
        delete this;
        // 그 후 자기자신 삭제.
    }
};
ListNode::ListNode() {
    pPrev = this;
    pNext = this;
    iValue = 0;
    // Single Linked List 에서는 pNext 에 NULL 을 넣어주었지만
    // Double Linked List 에서는 위 이미지와 같이  끝까지 간뒤에 다시 처음으로
    // 되돌아 오는 구조이기 때문에 일단 노드들을 만들 때 자기자신 혼자만 있다고 생각하고
    // 자신의 이전(pPrev)과 다음(pNext)이 자신을 가리키게끔 만들어둔다.
}
ListNode:: ListNode(int x) {
    iValue = x;
    pPrev = this;
    pNext = this;
    // Single Linked List 에서는 pNext 에 NULL 을 넣어주었지만
    // Double Linked List 에서는 위 이미지와 같이  끝까지 간뒤에 다시 처음으로
    // 되돌아 오는 구조이기 때문에 일단 노드들을 만들 때 자기자신 혼자만 있다고 생각하고
    // 자신의 이전(pPrev)과 다음(pNext)이 자신을 가리키게끔 만들어둔다.
}
 
 
class LinkedList{
private:
    ListNode* pHead;
    // Double Linked List 의 처음(Head)를 가리킬 포인터.
    int iCount;
    // 현재 가지고있는 노드들의 개수를 저장할 정수형 변수.
public:
    LinkedList();
    void addFirst(int x);
    void addLast(int x);
    int size() {
        return iCount;
    }
    bool isEmpty();
 
    friend ostream& operator<<(ostream& outs, LinkedList& l);
};
 
LinkedList::LinkedList() {
    pHead = NULL;
    iCount = 0;
}
 
void LinkedList::addLast(int x) {
    //리스트의 마지막에 노드하나 삽입.
    ListNode* pNewNode = new ListNode(x);
    iCount++;
    if(pHead == NULL){
        // 리스트가 비어있을때에는 pHead가 NULL이기 때문에
        pHead = pNewNode; // 바로 직접적으로 가리키게 하고 
        return;//끝
    }
    pNewNode->insert(pHead);
    //pHead가 List의 처음을 가리키고 있기때문에
    //처음의 이전 = 마지막 이기때문에
    //insert를 통하여 pHead의 이전에 넣어주면 마지막에 넣는걸로 된다.
}
 
void LinkedList::addFirst(int x){
    addLast(x); // 추가를 원하는 노드를 마지막에 넣어놓고
    pHead = pHead->getpPrev();
    //처음을 Head의 이전을 가리키게 해주면
    // 마지막이 처음이 되면서 처음을 가리키는것 처럼 된다.
}
bool LinkedList::isEmpty() {
    if( pHead == NULL) return true;
    else return false;
}
 
ostream& operator<<(ostream& outs, LinkedList &l) {
    if(l.isEmpty()){ //만약 비어있다면
        cout << " { }";
        return outs;
    }
    cout << " { ";
    ListNode* pNode = l.pHead;
    for(int i = 0; i < l.iCount; i++) {
        //Single Linked List에서는 While문으로 Next가 NULL일때까지를 확인했지만
        // Double Linked List에서는NULL이 없기때문에 for문으로 노드 갯수만큼만 돌게해준다.
        cout << pNode->getiValue() << " ";
        pNode = pNode->getpNext();
    }
    cout << "} ";
    return outs;
}
 
void main()
{
    LinkedList l;
    cout << l << endl;
    if(l.isEmpty()) {
        cout << "Empty !"<<endl;
    }else {
        cout << "Not Empty !"<<endl;
    }
    l.addFirst(10);
    cout << l << endl;
    l.addFirst(20);
    cout << l << endl;
    l.addFirst(30);
    cout << l << endl;
    l.addLast(40);
    cout << l << endl;
    l.addLast(50);
    cout << l << endl;
    cout << l.size() << endl;
    if(l.isEmpty()) {
        cout << "Empty !"<<endl;
    }else {
        cout << "Not Empty !"<<endl;
    }
}