요즘 코딩을 잘 안하는 것 같아 자료구조 중 링크드 리스트를 코딩해 보면서 공부 하기로 했다.
그래서 오늘은 간단하게 링크드 리스트 구조를 설계하고 원소를 왼쪽, 오른쪽으로 각각 삽입하는 기능을 구현해보도록 하겠다.
구현하기에 앞서 어떤 순서로 시작할지 대략 생각해 보면
1. 노드를 일단 만든다.
노드는 데이터와 next라는 것을 지닌다. 여기서 next 는 다음 노드를 가리키는 포인터변수다.
Node
2. 링크드 리스트 클래스를 만든다.
멤버변수 : 링크드 리스트의 시작위치를 알려주는 start, 끝의 위치를 알려주는 end
함수 : 왼쪽 삽입, 오른쪽 삽입, 리스트 출력
링크드 리스트 구조
3. 리스트 왼쪽 부분에 원소 추가 방법
- 추가할 원소 Next 를 다음 원소로 가리키게 하고 현재 링크드리스트의 start를 새로추가한 원소로 변경해준다. 그럼 왼쪽으로 추가가 된다.
4. 리스트 오른쪽 부분에 원소 추가 방법
- 현재 링크드리스트의 end부분 노드의 next 를 새로 만든 노드로 가리키게 해주면 된다. 그럼 오른쪽으로 원소가 추가가 된다.
5. 마지막으로 링크드리스트 원소를 전부 출력 해주는 방법은 C라는 변수를 두고 링크드 리스트의 start 부터 end 까지 순회시키면서 각 요소가 가진 데이터 전부를 출력하도록 한다.
이 절차대로 구현해주면 소스는 다음과 같다.
...더보기
#include <iostream>
#include <string>
#include <stdlib.h>
#include <vector>
using namespace std;
struct Node {
// 각원소
const char * data;
Node * next;
};
class myLinkedList {
public:
myLinkedList();
~myLinkedList();
void addLeft(const char*);
void addRight(const char*);
void getList();
private:
Node * start;
Node * end;
};
myLinkedList::myLinkedList() :start(NULL), end(NULL) {};
myLinkedList::~myLinkedList() {
}
void myLinkedList::addLeft(const char* data) {
Node * pTemp = (Node *)malloc(sizeof(Node));
pTemp->data = data;
pTemp->next = NULL;
if (this->start == NULL) {
this->start = pTemp;
this->end = pTemp;
}
else {
pTemp->next = this->start;
this->start = pTemp;
}
}
void myLinkedList::addRight(const char* data) {
Node * pTemp = (Node *)malloc(sizeof(Node));
pTemp->data = data;
pTemp->next = NULL;
if (this->start == NULL) {
this->start = pTemp;
this->end = pTemp;
}
else {
this->end->next = pTemp;
this->end = pTemp;
}
}
void myLinkedList::getList() {
Node * c;
Node result[100];
int index = 1;
c = this->start;
while (c != NULL) {
cout << index << "번째 data : " << c->data << endl;
index++;
c = c->next;
}
}
int main(){
Node * result = NULL;
myLinkedList myLinkPipe;
myLinkPipe.addLeft("red");
myLinkPipe.addLeft("blue");
myLinkPipe.addLeft("green");
myLinkPipe.addRight("black");
myLinkPipe.addRight("purple");
myLinkPipe.getList();
return 0;
}
