• Node들과 head 하나로 구성된다.
• Node는 저장 공간의 한 단위로, 데이터 저장 공간과 포인터로 구성된다.
• Node의 포인터에는 다음 노드의 주소가 저장되어 있다.
• head는 첫 번째 노드의 주소를 저장하는 포인터이다.
• 위 그림은 값 12, 99, 37을 순서대로 저장하는 Linked List를 그림으로 나타낸 것이다. 데이터로 12가 저장된 노드의 포인터는 99가 저장된 다음 노드의 주소를 저장하고 있다.
• 위 그림에서, head에는 12가 저장된 노드의 주소가 저장되어 있을 것이다.

class Node {
    int data;
    Node *n;
};

class List {
    List();
    ~List();
    int Search();
    int Insert();
    int Delete();

    Node *head;
    /* 다음 p, l은 search에 사용할 포인터이다.
       검색에 성공할 경우, l에는 검색한 값을 가지는 노드의 주소가 저장되고, p에는 그 이전 노드의 주소기 저장된다.
       검색에 실패할 경우, p와 l이 가리키는 노드 사이에 검색값이 삽입되야 정렬된 상태를 유지하도록, p와 l값이 정해진다. */
    Node *p, *l;
};

List::List() {
    head = nullptr;
}

List::~List() {
    Node *current, *next;
    current = head;
    while(current != nullptr) {
        next = current->n;
        delete current;
        current = next;
    }
}

/* Search는 Linear Search 알고리즘을 이용한다.
   linked list는 중간 노드에 바로 접근할 수 없으므로, binary search를 빠르게 할 수 없다. */
int List::Search(int x) {
    p = nullptr;
    l = head;
    while(l != nullptr) {
        if(l->data == x) return 1;
        else if(l->data > x) return 0;
        else {
            p = l; l = l->n;
        }
    }
    return 0;
}

int List::Insert(int x) {
    if(!Search(x)) {  // 중복값을 막기 위해 검색에 실패했을 때만 Insert
        Node* new_node = new Node;
        new_node->data = x;
        if(p == nullptr)
            head = new_node;
        else
            p->n = new_node;
        new_node->n = l;
        return 1;
    }
    return 0;
}
       
List::Delete(int x) {
    if(Search(x)) {
        if(p==nullptr)
            head = l->n;
        else
            p->n = l->n;
        delete l;
        return 1;
    }
    return 0;
}

• 정렬된 리스트의 경우
• 정렬되어 있어도 인덱스의 중간값에 바로 접근할 수 없으므로 binary search 불가.
• Search : O(n)
• Inseart : S + O(1)  (S는 search 에 걸리는 시간)
• Delete : S + O(1)
• 정렬되지 않은 리스트의 경우
• Search : O(n)
• Insert : O(1) (정렬을 유지할 필요가 없으므로, Search 없이 그냥 head에 노드를 추가하면 됨)
• Delete : S + O(1)

Skip List에 대한 아이디어