2. 링크드 리스트 [Linked List]

Why?

1. 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점이 있기 때문.

 

How?

1. 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당

2. 링크드 리스트의 종류

  2-1.  단일 연결 리스트

출처 : 위키피디아

#include <iostream>
using namespace std;
//Linked List
//https://hojak99.tistory.com/274
class Node{
    public : Node *nextNode = nullptr;
    int data;
};

class Link {
    public : Node *head = new Node();
    void insert(Link *linkedList, int data);
    void printList(Link *linkedList);
};

void Link::insert(Link *linkedList, int data){
    Node *newNode = new Node;
    newNode->data = data;
    newNode->nextNode = nullptr;
    
    if(head->nextNode == nullptr){
        head->nextNode = newNode;
    }else{
        Node *currNode = head;
        while(currNode->nextNode != nullptr){
            currNode = currNode->nextNode;
        }
        currNode->nextNode = newNode;
    }
}
void Link::printList(Link *linkedList){
    Node *tmpNode = head->nextNode; //head 는 nullptr로 쓰고 그 뒤부터
    while(tmpNode != nullptr){
        cout<< tmpNode->data << endl;
        tmpNode = tmpNode->nextNode;
    }
}

int main(){
    Link *linkedList = new Link();
    linkedList->insert(linkedList, 4);
    linkedList->insert(linkedList, 1);
    linkedList->insert(linkedList, 5);
    linkedList->insert(linkedList, -1);
    
    linkedList->printList(linkedList);
    
    return 0;
}

  2-2. 이중 연결 리스트

출처 : 위키피디아

  2-3. 원형 연결 리스트

출처 : 위키피디아

Plus

1. 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점 존재.

 

Problem

1.

2.

 

계속 수정 예정. 2019.04.14 수정됨.