List 실습

Singly LinkedList

Node

1. data : 값2. next  : 다음노드 포인터 (초기값 : NULL)

1. append(val)

- 새로운 노드를 생성한다

- 값 val을 저장한다

- tail에 새로생성된 노드를 넣는다

 

2. delete(index)

- 리스트가 비어있는지 확인한다 (비어있는 경우 특정값 반환 후 종료한다)

- head 부터 한칸씩 이동하면서 이전노드 = u, 해당노드 = p를 각각 저장한다

- p가 index 위치에 도달한경우

- p의 다음노드를 w로 저장한다

- u의 next를 w로 설정한다

- p를 제거한다

 

Doubly LinkedList

Node

1. data : 값

2. next : 다음노드 포인터

3. pre : 이전노드 포인터

1. empty()

- 리스트가 비어있는지 여부를 반환한다

 

2. List_size()

- 리스트의 개수를 반환한다

 

3. append(val)

- 새로운 노드를 생성한다

- 값 val을 저장한다

- tail에 새로생성된 노드를 넣는다

 

4. add_front(val)

- 새로운 노드를 생성한다

- 값 val을 저장한다

- 노드의 next를 head 값으로 저장한다

- head를 노드로 수정한다

 

5. insert(idx, val)

- 새로운 노드 v를 생성한다

- 값 val을 저장한다

- head 부터 한칸씩 이동하면서 이전노드 = u, 해당노드 = p로 저장한다

- idx 위치에 도달한경우 

- u의 next = v로 설정한다

- v의 pre = u로 설정한다

- v의 next = p로 설정한다

- p의 pre = v로 설정한다

 

6. delete(idx)

- head부터 한칸씩 이동하면서 이전노드 = u, 해당노드 = p로 저장한다

- idx 위치에 도달한 경우 다음노드를 w로 저장한다

- u의 next = w로 설정한다

- w의 pre = u로 설정한다

- p를 제거한다

 

7. print()

- head 부터 차례로 돌면서 val 값을 출력한다

 

8. Class Node (for Singly LinkedList)

class Node {
public:
    int data; //노드의 값
    Node* next; //다음노드 포인터
    
    Node(int data) { //노드의 생성자, 초기값을 받는다
        this->data = data; //값을 입력받은 값으로 저장한다
        this->next = NULL; //초기 포인터값을 NULL 값으로 저장한다
    }
};

 

9. Class Singly LinkedList

class Singly_LinkedList {
public:
    Node* head; //머리 포인터
    Node* tail; //꼬리 포인터
    
    Singly_LinkedList() { //단일리스트의 생성자, 초기값을 받지 않는다
        this->head = NULL; //초기 머리포인터를 NULL 값으로 저장한다
        this->tail = NULL; //초기 꼬리포인터를 NULL 값으로 저장한다
    }
    
    //여기서부터 list의 function들
    //1. 리스트가 비었는지 여부를 반환한다
    int empty() {
        if(head == NULL && tail == NULL) {
            return 1; //머리, 꼬리 포인터가 초기값인경우 1 반환
        }
        else
            return 0; //노드가 있는경우 0 반환
    }
    
    //2. 리스트 개수를 반환한다
    int size() {
        int size = 1;
        Node* cur_node = head;
        if(empty()) {
            return 0; //만약 빈경우 개수 0을 반환한다
        }
        else {
            while(cur_node != tail) { //head 노드부터 tail 노드가 되기전까지 반복하여
                cur_node = cur_node->next;
                size++;  //개수를 증가시킨다
            }
            return size;
        }
    }
    
    //3. 리스트의 내용을 출력한다
    void print() {
        Node* cur_node = head;
        if(empty()) {
            cout<<-1; //만약 리스트가 비어있는경우 -1을 출력한다
        }
        else {
            while(cur_node != tail) { //head 부터 tail까지 반복하여
                cout<<cur_node->data<<" "; //노드의 값을 출력한다
                cur_node = cur_node->next;
            }
        }
    }
    
    //4. 노드를 추가한다
    void append(int data) {
        if(empty()) { //리스트가 없는경우
            Node* v = new Node(data); //새로운 리스트를 생성하여
            this->head = v; //head로 설정한다
            this->tail = v; //tail로 설정한다
        }
        else { //리스트가 있는경우
            Node* v = new Node(data); //새로운 리스트를 생성하여
            this->tail->next = v; //tail노드의 다음노드에 연결한다
            this->tail = v; //tail을 새로운 노드로 설정한다
        }
    }
    
    //5. 노드를 삭제한다
    int del(int idx) {
        if(empty()) {
            return -1; //만약 리스트가 비어있는경우 -1을 반환한다
        }
        else {
            Node* p = head; //idx 대상 노드를 p로 저장한다
            Node* u; //p의 이전노드를 u로 저장한다
            Node* w; //p의 다음노드를 w로 저장한다
            int location = 0;
            while(location != idx) { //idx 위치까지 올라가면서
                u = p; //u를 저장한다
                p = p->next; //p를 저장한다
            }
            w = p->next; //idx위치에 도달한 경우 p의 다음노드를 w로 저장한다
            u->next = w; //u -> p -> w : u -> w로 설정한다
            int temp = p->data; //p의 값을 저장한다
            delete p; //p를 삭제한다
            return temp; //p의 값을 반환한다
        }
        
    }
    
    //6. idx 위치에 새로운 노드를 넣는다
    void insert(int idx, int data) {
        Node* new_node = new Node(data); //새로운 노드를 생성한다
        if(idx == 0) { //만약 head 위치에 넣을경우
            if(empty()) { //리스트에 노드가 없는경우
                this->head = new_node; //새로운 노드를 head로 설정한다
                this->tail = new_node; //새로운 노드를 tail로 설정한다
            }
            else { //리스트에 노드가 있는경우
                new_node->next = head; //새로운 노드의 next를 head로 설정한다
                this->head = new_node; //head를 새로운 노드로 설정한다
            }
        }
        else if(idx < 0 || idx > size()) { //idx가 정상범위가 아닌경우
            cout<<"no insert\n";
            return; //에러를 출력한뒤 반환한다
        }
        else if(idx == size()) { //idx가 마지막 위치인 경우
            append(data); //tail 위치에 넣는다
        }
        else { //리스트의 중간위치에 넣는경우
            Node* p = head; //idx 위치의 노드를 p로 저장한다
            Node* u; //p의 이전노드를 u로 저장한다
            int location = 0;
            while(location != idx) {
                u = p; //u를 저장한다
                p = p->next; //p를 저장한다
            }
            u->next = new_node; //p가 idx 위치인 경우 u의 next를 새로운 노드로 설정한다
            new_node->next = p; //새로운 노드의 next를 p로 설정한다
        }
    }
};