[자료구조] Linked Lists

• 개요 : 노드와 노드를 연결 시킨 자료구조, memory size를 변경 시키는데 용이하다. 노드에 포인터를 이용해 접근한다.
• Singly Linked List
  
  • 단일 연결 리스트, 노드들의 순열로 구성된 자료구조
  • 각 노드는 데이터(element)와 다음 노드를 가리키는 포인터 1개로 구성된다.
  • head는 가장 앞에 있는 노드를, tail은 가장 뒤에 있는 노드를 가리키는 포인터다.

#include <iostream>
#include <string>
using namespace std;

class Node{
private:
    Node* next;
    int data;
    
    friend class SinglyLinkedList;
};
class SinglyLinkedList{
private:
    Node* head;
    Node* tail;
    int listSize;
public:
    SinglyLinkedList(){
        head = nullptr;
        tail = nullptr;
        listSize = 0;
    }
    bool Empty(){// 링크드 리스트가 비어있는 지 판단하는 함수
        return (listSize==0);
    }
    void Append(int data){// 링크드 리스트 마지막에 data삽입하는 함수
        Node* newNode = new Node;
        newNode -> data = data;
        newNode -> next = NULL;
        
        if (Empty()){//링크드 리스트가 비어있는 경우
            head = tail = newNode;//head 와 tail은 모두 새로운 노드를 가리킴
        }
        else{//링크드 리스트가 비어있지 않으면
            tail->next = newNode;
            tail = newNode;//tail은 새로운 노드를 가리킴
        }
        listSize++;//새로운 노드가 추가 되었으므로 listsize증가
    }
    void Insert(int idx, int data){//링크드 리스트에 idx번째 노드에 data삽입하는 함수
        if(idx>listSize || idx <0){//idx가 범위를 벗어나는 경우에 대한 예외처리
            return;
        }
        else if(idx == listSize){//들어온 idx가 listsize와 같다면
            Append(data);//listsize번째에 추가는 마지막에 data 추가 하는 거랑 같음
        }
        else if(idx == 0){// idx가 0인 경우 listsize 0번째에 data삽입
            Node* newNode = new Node;
            newNode->data = data;
            newNode->next = head;//새로운 노드에 다음 노드는 기존에 가장 앞에있던 노드
            head = newNode;//head는 새로운 노드를 가리킴
            listSize++; //새로운 노드가 추가 되었으므로 listsize증가
        }
        else{//리스트 중간에 노드를 삽입하는 경우
            Node* curNode = new Node;
            curNode = head;//curNode는 index역할을 함
            for(int i=0;i<idx-1;i++){//head 부터 idx-1번째 노드까지 탐색
                curNode = curNode->next;
            }
            Node* newNode = new Node;
            newNode->next = curNode->next;//추가할 노드에 다음 노드는 curNode의 다음 노드
            newNode->data = data;
            curNode->next = newNode;//curNode의 다음 노드는 새로운 노드
            listSize++; //새로운 노드가 추가 되었으므로 listsize증가
        }
    }
    void Delete(int idx){
        if(idx>listSize || idx <0){//idx가 범위를 벗어나는 경우에 대한 예외처리
            return;
        }
        if(idx==0){//맨 앞에 있는 노드를 제거하는 경우
            if(listSize==1){//노드가 하나밖에 없는 경우
                head=tail=NULL;//head 와 tail 모두 NULL
            }
            else {
                head = head->next;//head는 head 다음노드를 가리킴
            }
            listSize--;//노드 삭제 됐으므로 listSize감소
        }
        else{
            Node* preNode = new Node;//삭제할 노드의 이전노드
            Node* deleteNode = new Node;//삭제할 노드
            preNode = head;
            for(int i=0;i<idx-1;i++){//head부터 삭제할 노드 전 노드까지 탐색
                preNode = preNode->next;
                deleteNode = preNode->next;
            }
            preNode->next = deleteNode->next;//이제 preNode의 다음노드는 삭제할 노드의 다음노드
            if(deleteNode == tail){//삭제할 노드가 tail이 가리키는 노드일 경우
                tail = preNode;//이제 tail은 preNode를 가리킴
            }
            delete deleteNode;//deleteNode삭제
            listSize--;//노드 삭제 됐으므로 listSize 감소
        }
    }
    void Print(){
        if(Empty()){//리스트 비어있는 경우
            cout<<"Empty"<<endl;
        }
        else{
            Node* curNode = new Node;
            curNode = head;
            for(int i=0; i<listSize; i++){//head부터 리스트 탐색
                cout<< curNode->data <<" ";//해당 노드의 data 출력
                curNode = curNode->next;
            }
            cout<<endl;
        }
    }
};
int main() {
    SinglyLinkedList L = SinglyLinkedList();
    int n = 0;
    cin >> n;
    while(n--){
        string cmd;
        cin >> cmd;
        if(cmd == "Append"){
            int data;
            cin >> data;
            L.Append(data);
        }
        else if(cmd == "Insert"){
            int index;
            int data;
            cin >> index;
            cin >> data;
            L.Insert(index,data);
        }
        else if (cmd == "Delete"){
            int index;
            cin >> index;
            L.Delete(index);
        }
        else if (cmd == "Print"){
            L.Print();
        }
    }
    
}

• Double Linked List
  • 이중 연결 리스트, 노드들의 순열로 구성된 자료구조
  • 각 노드는 데이터(element)와 다음 노드를 가리키는 포인터, 이전 노드를 가리키는 포인터로 구성된다.
  • head는 가장 앞에 있는 노드를, tail은 가장 뒤에 있는 노드를 가리키는 포인터다.