[C++] Linked list

1. 연결 리스트

 

요소가 인접한 메모리 위치에 저장되지 않는 선형 데이터 구조다.

 

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조다.

 

//sigle list의 node
class Node {
public:
    int data;
    Node* next;
    Node(){
        data = 0;
        next = NULL;
    }
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

인접한 메모리 위치에 저장되지 않아서 공간 효율성이 높지만 반대로 인접한 메모리 위치에 저장되지 않기 때문에 순차적 접근이 강제된다.

 

이에 검색에 있어서 O(n)만큼의 시간이 소요된다.

 

연결리스트는 싱글연결리스트, 이중연결리스트, 원형싱글연결리스트 그리고 원형이중연결리스트 등이 있다.

 

 

---

2. list

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

list<int> a;
void print(list<int> a){
    for(auto it : a) cout << it << " ";
    cout << endl;
}
int main(){
    for(int i=1; i<=3; i++)a.push_back(i);
    for(int i=1; i<=3; i++)a.push_front(i);

    auto it = a.begin();
    it++;
    a.insert(it, 100);
    print(a);

    it = a.begin();
    it++;
    a.erase(it);
    print(a);

    a.pop_front();
    a.pop_back();
    print(a);

    cout << a.front() << " : " << a.back() << endl;
    a.clear();
    return 0;
}
/*
3 100 2 1 1 2 3 
3 2 1 1 2 3 
2 1 1 2 
2 : 2
*/

• list<int> a; : 리스트 선언
• a.push_back(i); : 뒤에 새로운 요소 추가.
• a.push_front(i); : vector나 array에는 없는 기능이다. 앞에서부터 새로운 요소를 추가할 수 있다.
• a.insert(it, 100); : 주어진 iterator에 주어진 값을 삽입한다.
• a.erase(it); : 주어진 iterator의 요소를 삭제한다.
• a.pop_front(); : 앞에서부터 삭제한다.
• a.pop_back(); : 뒤에서부터 삭제한다.
• a.front(), a.back(), a.clear(); 리스트도 사용할 수 있다.

 

---