여러 데이터를 사용하는 경우
데이터를 필요한 만큼 사용하는 자료구조, 데이터가 순차적으로 이어져 있는 선형 구조
두가지의 필드로 구성되어 있다.
👍
👎
class node {
private:
int val;
node *next;
public:
node(int val) {
this->val = val;
next = nullptr;
}
void setNext(node *nextNode) {
this->next = nextNode;
}
node *getNext() {
return next;
}
int getVal() {
return val;
}
};
class linkedList {
public:
linkedList();
bool empty();
void append(int val);
void insert(int idx, int val);
int erase(int idx);
void print();
void updateSize(int n);
void getMin();
private:
node *head;
node *tail;
int size;
};
linkedList() { // 기본 생성자, 초기화
head = nullptr;
tail = nullptr;
size = 0;
}
updateSize(int n) {
size += n;
}
bool linkedList::empty() {
if (size == 0) {
return true;
}
return false;
}
맨뒤에 추가하기
void linkedList::append(int val) {
node *newNode = new node(val);
if (empty()) {
head = tail = newNode;
} else {
tail->setNext(newNode);
tail = newNode;
}
updateSize(1);
}
노드를 삽입할 때 변하는 값을 주의하자
맨뒤에 삽입하는 경우 : append() 활용
맨앞인 경우 :
나머지 경우 :
insert(int idx, int val) {
// index 검증
if (idx < 0 || idx > size) {
// index 는 0보다 작거나 크기 보다 클 수 없어요
cout << "Index Error" << "\n";
return;
}
if (idx == size) {
//idx == size -> 맨 뒤
append(val);
} else if (idx == 0) {
node *newNode = new node(val);
newNode->setNext(head);
head = newNode;
updateSize(1);
} else {
node *newNode = new node(val);
node *curNode = head;
for (int i = 0; i < idx - 1; i++) {
curNode = curNode->getNext();
}
newNode->setNext(curNode->getNext());
curNode->setNext(newNode);
updateSize(1);
}
}
삭제하려는 위치를 찾는다.
해당 노드를 삭제한다.
erase(int idx) {
if (idx < 0 || idx >= size) {
// index 는 0보다 작거나 크기 보다 크거나 같을 수 없어요
return -1;
}
if (empty()) {
// 비어있으면 삭제 할 수 없겠죠?
return -1;
}
node *delNode;
if(idx == 0){
delNode = head;
if(size == 0){
head = nullptr;
}else{
head = head->getNext();
}
}else{
node *curNode = head;
for (int i = 0; i < idx - 1; i++) {
curNode = curNode->getNext();
}
delNode = curNode->getNext();
curNode->setNext(delNode->getNext());
if(delNode == tail){
tail = curNode;
}
}
int val = delNode->getVal();
delete delNode;
updateSize(-1);
return val;
}
getMin() {
if (empty()) {
cout << "empty";
return;
}
int min = head->getVal();
node *curNode = head;
for (int i = 0; i < size; i++) {
if (curNode->getVal() < min)
min = curNode->getVal();
curNode = curNode->getNext();
}
cout << min;
}
print() {
if (empty()) {
cout << "empty";
return;
}
node *curNode = head;
for (int i = 0; i < size; i++) {
cout << curNode->getVal() << " ";
curNode = curNode->getNext();
}
}