Linked_List

연결 리스트!

 

음 연결리스트란 것은 요소들이 서로 인접한 메모리 위치에 저장되지 않는 선형 자료 구조입니다.

 

한마디로 주변에 서로 없다는 거죠.

랜덤 접근도 불가능하고 오로지 순차적으로만 접근이 가능해요.

 

각 요소들을 접근하려면 next, prev라는 포인터로 연결이 되어있고 중복은 가능합니다.

 

그렇다면 이렇게 하면 장점이 뭘까요?

 

이는 공간적인 효율성이 좋습니다.

뭐 예를 들어 배열에서 중간 데이터를 삭제한다면 

이런식으로 삭제가 되서 다시 재배치가 되겠죠?

하지만 연결리스트는 다릅니다.

 

삭제를 하면 그 요소의 next와 prev포인터를 변경만 시켜주면 되죠.

삽입 또한 똑같아요.

 

2번째에 삽입하려면 이 방식으로 삽입하고 다시 재배치 하겠죠.

 

연결리스트의 삽입은

네 포인터만 바꿔주면 되요.

 

그래서 삽입과 삭제의 시간복잡도는 O(1)입니다.

그리고 n번째 요소를 참조한다 했을 때는 O(n)이 거립니다.

 

List의 내부 구조는 이렇습니다.

아래는 싱글리스트

class Node
{
public:
    int data;
    Node* next;
    
    Node()
    {
        data = 0;
        next = NULL;
    }
    
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
}

 

이중 연결 리스트는

class Node
{
public:
    int data;
    Node* next;
    Node* prev;
    Node()
    {
        data = 0;
        next = NULL;
        prev = NULL;
    }
    
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
        this->prev = NULL;
    }
}

 

prev라는 포인터가 하나 더 추가 된 것입니다.

 

연결리스트의 종류는 총 3가지가 있어요.

싱글 연결리스트, 이중 연결리스트, 원형 연결리스트 이렇게 3가지가 있습니다.

 

싱글 연결 리스트(Singly Linked List)

next 포인터밖에 존재하지 않아서 한 방향으로만 데이터가 연결이 됩니다.

 

 

이중 연결 리스트(Doubly Linked List)

이중 연결 리스트는 prev, next 두개의 포인터로 양 방향으로 데이터가 연결이 됩니다.

원형 연결 리스트(Circular Linked List)

원형 연결리스트는 마지막 노드와 첫번째 노드가 연결이 되어 원을 형성해요.

아래는 원형 싱글 연결리스트이며

 

 

이거는 원형 이중 연결 리스트입니다.

쉽죠?

그.. 이게 보다보면 익숙해져서 아! 할 때가 있더라구요..

저는 지금 되게 이해가 쏙쏙 되거든요...ㅎ...

 

그러면 C++에서 list로 이중 연결 리스트를 구현해봅시다.

 

#include <iostream>
#include <list>

using namespace std;


void print(list <int> _list)
{
    for (auto it : _list)
        cout << it << " ";
        
    cout << '\n';
}

int main()
{
    list<int> li;

    for (int i = 1; i <= 3; ++i)
        li.push_back(i);
        
    for (int i = 1; i <= 3; ++i)
        li.push_front(i);
        
    auto it = li.begin();
    it++;
    
    li.insert(it, 1000);
    print(li);
    
    it = li.begin();
    it++;
    li.erase(it);
    print(li);
    
    li.pop_front();
    li.pop_back();
    print(li);
    
    cout << li.front() << " : " << li.back() << '\n';
    
    li.clear();
    
    return 0;
}

 

이것도 예상해보면서 결과값이 어떨지 예상해보는 것이 좋습니다.

 

그럼 여기서 사용된 list의 함수들을 살펴봅시다.

 

진짜이번엔 간단하게 갈겁니다!!

 

push_front(value)

list의 앞에서 value 삽입

 

push_back(value)

list의 뒤에서부터 value 삽입

 

insert(이터레이터 위치, value)

물론 idx는 이터레이터를 넣는 부분이다.

iterator insert (const_iterator position, const value_type& val);

몇번째의 요소의 value를 삽입

 

erase(이터레이터 위치)

iterator erase (const_iterator position);

list의 이터레이터의위치의 요소를 지움

 

 

pop_front()

첫번째의 요소를 지움

pop_back()

맨 끝 요소를 지움

front()

맨 앞 요소를 참조

back()

맨 뒤 요소를 참조

clear()

list의 모든 요소들을 지움

 

끄으트으트ㅡㅇㅌ