#include <iostream>
using namespace std;
typedef struct tagNode{ // typedef 는 c++ 에서는 안써도 되지만 C언어와의 호환을 위해 사용해주는 것이 좋다.
tagNode* nextNode = NULL;
int data;
}Node;
Node* CreateNode(int newData){
Node* newNode = (Node*) malloc(sizeof(Node)); // 자유저장소애 Node 를 할당한다.
newNode -> data = newData;
return newNode;
}
void appendNode(Node** Head, Node* newNode){ // 여기서의 Node** Head 는 Head노드의 주소 값이다. 일단 Head노드 자체가 Node 구조를 가지는 구조체의 주소 값이고 Node** Head는 그 주소를 담고있는 주소값이다. (그런데 꼭 이렇게 나타내야 하는 것인가?? ) 이렇게 하는 이유는 첫 해드가 비어 있을 때 newNode 가 헤드가 되는데 이중포인터를 쓰지 않고 하면 함수 밖으로 나왔을 때에 변한 값이 저장 되지 않는다.
if((*Head) == NULL){
*Head = newNode;
}else{
Node* tmp = (*Head); // *Head -> nextNode 이렇게 쓰면 안됩니다. (*Head) -> nextNode 가 맞는표현
while(tmp -> nextNode != NULL){
tmp = tmp -> nextNode;
}
tmp -> nextNode = newNode;
}
}
void removeNode(Node** Head, Node* Remove){
if((*Head) == Remove){
*Head = Remove -> nextNode;
}else{
Node* tmp = (*Head);
while(tmp -> nextNode != Remove && tmp != NULL){
tmp = tmp -> nextNode; // 여기에서 제거해야하는 노드의 전 노드를 찾는다.
}
if( tmp != NULL){
tmp -> nextNode = Remove -> nextNode; // 제거 하려는 노드의 전 노드와 제거 하려는 노드의 다음 노드를 이어 준다.
}
}
}
void destroyNode(Node* node){
free(node);
}
Node* findNode(Node* Head, int index){
Node* Current = Head;
while((--index) >= 0 && Current != NULL){ // 찾고자하는 것이 없으면 NULL Current 가 NULL 이 된다.
Current = Current -> nextNode;
}
return Current;
}
void insertNode(Node* Current, Node* newNode){
newNode -> nextNode = Current -> nextNode;
Current -> nextNode = newNode;
}
int main(){
Node* List = NULL;
Node* newNode = NULL;
newNode = CreateNode(117);
appendNode(&List, newNode);
newNode = CreateNode(110);
appendNode(&List, newNode);
Node* ans = findNode(List, 3);
cout << ans -> data;
return 0;
}
위는 기본적인 링크드 리스트를 구현 한것이다. 링크드 리스트의 장점은 추가, 삽입, 삭제가 쉽다. 여기서 일반적인 연결리스트의 추가는 끝까지 돌기 때문에 배열보다 좋지 않다고 생각이 들지만, 환형리스트를 이용하면 추가를 한번에 할 수 있고, 배열은 맨처음에 용량을 정하지만, 연결리스트는 정하지 않고 계속해서 확장해 나아갈 수 있다..
링크드 리스트의 단점은 특정한 위치의 노드의 값을 찾는데에 시간이 든다는 것이다 배열은 한번에 찾아갈 수 있는 반면에 연결리스트는 최악의 경우 n 번을 다 돌수도 있다.
위에서의 환형리스트란? node 구조체를 만들때에 다음노드만 생성하는 것이 아니라 이전 노드도 저장하도록 한다. 또한, 마지막 노드와 맨 처음 해드 노드를 이어서 추가 append를 할 때에 위에서 처럼 찾아가는 것 대신에 마지막 노드와 맨 처음 노드 사이에 끼워 넣을 수 있다.