자료구조 및 알고리즘 7 - LinkedList

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다.

 

0. LinkedList

 

LinkedList 는 Node 들로 구성되어있는 자료구조입니다. 노드는 저장요소들의 단위로 노드들을 포인터를 통해 서로 연결되어있습니다. 그래서 연결 리스트라 불립니다. 연결 리스트의 구조는 다음과 같습니다.

연결리스트 구조

 

연결 리스트에는 head 라는 포인터를 통해 처음 요소를 가르킵니다. 또한 마지막 노드의 next 포인터는 null 값을 가르킴으로써 마지막 요소임을 나타냅니다.

 

#include <iostream>

class Node{
public:   
    Node(int data)
    : data{data}, next{NULL}{};

    ~Node(){
        std::cout << data << "삭제" << std::endl;
    }

    int data;
    Node *next;
};

class List{
public:
    List();
    ~List();
    void makeNode(int data);
    int Search(int x, Node **p, Node **l);
    int Insert(int x);
    int Delete(int x);

    Node *head;
};

void List::makeNode(int data){
    if(head == NULL)
        head = new Node(data);
    else{
        Node *newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }
}

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

List::~List(){
    Node *p, *q;
    p = head;
    while(p != NULL){
        q = p->next;
        delete p;
        p = q;
    }
}

int List::Search(int x, Node **p, Node **l){
    *p = NULL;
    *l = head;

    while(*l != NULL){
        if((*l)->data == x)
            return 1;
        else if((*l)->data < x){
            *p = *l;
            *l = (*l)->next;
        }
        else{
            return -1;
        }
    }
    return -1;
}

int List::Insert(int x){
    Node *p, *l;
    int result = Search(x, &p, &l);

    if(result != -1)
        return -1;
    
    if(p == NULL){
        // 가장 앞에 Insert
        Node *newNode = new Node(x);
        newNode->next = head;
        head = newNode;
    }
    else{
        Node *newNode = new Node(x);
        newNode->next = l;
        p->next = newNode;
    }

    return 0;
}

int List::Delete(int x){
    Node *p, *l;
    int result = Search(x, &p, &l);

    if(result == -1)
        return -1;

    if(p == NULL){
        head = l->next;
        delete l;
    }
    else{
        p->next = l->next;
        delete l;
    }

    return 0;
}

 

(*

@Assuming : LinkedList 의 각 노드들의 값은 오름차순으로 정렬되어있고, 중복된 값을 갖지 않습니다.

@param p: 찾는 노드의 이전 노드, 만약 찾는 노드가 head 노드라면 p 는 null 값을 갖는다.

    여기에서 Dummy Node 를 head 노드로 넣는다면 p 가 null 인 경우의 예외처리는 하지 않아도 됩니다.

@param l: 찾는 노드, 만약 찾는 노드가 없다면 Insert 해야하는 자리의 뒷 노드를 갖습니다.

)

 

1. Performance

 

Search : O(N), 그냥 linear search 보다는 빠른 O(N) 입니다.

Insert : S + O(1)

Delete : S + O(1)

 

2. Comparison with std::vector

 

Vector : Variable-Size Array

• Sorted-Vector
  
  • Search : O(logN), Insert : S + O(n), Delete : S + O(n)
• Unsorted-Vector
  • Search : O(n), Insert : S + O(1), Delete : S + O(1)