list와 list의 이터레이터

※ 개인적인 공부를 위해 포스팅 하는 글입니다.

---

list는 한마디로 양방향 연결 리스트

 

list의 동작 원리

중간 삽입/삭제

처음/끝 삽입/삭제

인덱스 접근

 

★ 동작 원리

 

 list는 단일,이중,원형 <-- 뭔소리냐?

이중 리스트

ㆍ std::list는 양방향 연결 리스트(이중 리스트)로 구현되어있다. 

 

ㆍ 벡터는 [           ] 메모리 공간에 요소들이 연속적으로 나열되어 있었다...

 

ㆍ 1개의 인자들이 있는 공간은(단위) 노드 라고 부르며 노드들은 본인 기준으로 이전노드와 다음노드의 포인터를 가지고 있다!

class Node
{
public:
    Node* _next;
    Node* _prev;
    int _data;
};

ㆍ 이런식으로 기초 설계도를 작성해 볼 수 있겠다. 이런 노드들의 집합이 list 컨테이너다.

 

# 단일리스트 원형리스트??

 

ㆍ 사실 뭐 별건 아니다

 

1. 단일리스트

class Node
{
public:
    Node* _next;
    int _data;
};

 ㆍ 노드들이 한방향 정보만 가지고 있는 리스트

2. 원형리스트

 

ㆍ 마지막 노드포인터와 첫번째 노드 포인터를 서로의 포인터를 가진다면 그것이 원형리스트 

 

 

# 리스트 사용해보기

int main()
{
    list<int> li;
    for (int i = 0; i < 100; i++)
    {
        li.push_back(i);
    }
    li.push_front(10);
    int size = li.size();

    li.capacity; 동적배열이 아니기 때문에 용량의 개념이 없다.
    메모리 공간이 아니기때문에 용량이라는 개념이 없다.

    int first = li.front();
    int last = li.back();

    l[3] = 10; 안댐 임의접근 허용 x

    list<int>::iterator it; //벡터의 이터레이터랑 다르게 동작한다.
    list<int>::iterator itBegin = li.begin(); 
    list<int>::iterator itEnd = li.end();

    for (list<int>::iterator it = li.begin(); it != li.end(); ++it)
    {
        cout << *it << endl;
    }

    li.insert(itBegin, 100);
    li.erase(li.begin());
    li.pop_back();
    li.remove(10); 
    // 이 값과 같은 모든 요소를 삭제한다! 리스트는 중간 삽입 삭제가 효율적이기 떄문에 다양한 것을 지원하는 모습
}

 

 

# 중간 삽입 삭제 효율적.

ㆍ 삽입 삭제 관련해선 메모리 공간에 연속적으로 나열된 것이 아니기 때문에 어디서든 효율적으로 잘 작동한다.

ㆍ 노드들이 추가된다고 하더래도 메모리 공간을 밀어줄 필요도 없고 그냥 노드들의 포인터만 바꿔주면 되기 때문인듯

ㆍ 따라서 처음 삽입/삭제든, 중간 삽입/삭제든 차이가 없다.(효율적) 삽입,삭제와 관련된 함수들을 많이 지원한다.

 

# 인덱스 접근 허용하지 않음

ㆍ 인덱스 임의 접근은 허용하지 않는다.

ㆍ 벡터는 연속적인 공간이라 인덱스 접근이 가능했었다.

ㆍ 리스트는 각 노드들이 포인터로 다음노드, 이전노드를 가지고 있는 것 이기 때문에

     ↘(먼 공간에 그저 포인터만 가지고있을뿐)

인덱스 임의 접근을 할 수 없는것이다. (한땀... 한땀...순차 접근만 가능)

 

 

 

#눈으로 확인해보고싶다

▶ 이전노드... 다음노드... 메모리를 까봐서 눈으로 직접 확인해 보자

 

ㆍ 직접 메모리를 타고 들어가보니 이론적으로 본 내용들이 있다!

 

 

#아니 근데 궁금한게... 첫번째 값 10은 왜 이전노드 포인터를 가지고있는거지?? 그래서 타고 들어가봤다

ㆍ 이상한값이 들어가있다.. 그래서 한번 더 이전 주소를 타고 가봤다.

ㆍ 내가 리스트에 저장해 뒀던 99라는 값이 16진수로 들어가있는 그 노드가 나왔다!!

☆ 더미 데이터를 이용해서 이터레이터의 end() 를 판별하는걸로 사용된다고 한다.

→ 더미는 판별해 주기 위해서 있는 메모리 공간이다. 따라서 직접 접근하려고 하면 프로그램이 터진다(내가 해봄)

list<int>::iterator itTest1 = --itBegin; //펑
list<int>::iterator itTest2 = --itEnd; //이건 마지막값으로 잘 됨 ㅎㅎ
list<int>::iterator itTest3 = ++itEnd; //펑

ㆍ end를 판별하는 용도로 사용되는 공간이다라고 알아두자

 

 

 

 

# 또 궁금한게 임의접근이 안되는데 중간 삽입/삭제는 빠르다..? 

ㆍ 50번 인덱스에 있는 데이터를 삭제해보자!

li.begin()+50; //안됨

당연한 말이지만 안된다. + - 연산자를 지원하지 않는 이유는 [1] ..... [50] 포인터로 그냥 들고있을 뿐 다른 메모리공간이기 때문이다.

  list<int>::iterator it = li.begin();
  for (int i = 0; i < 50; i++)
  {
      ++it;
  }//느림
  li.erase(it); //빠름

ㆍ 이런식으로 접근해야 한다. 분리해서 생각하자. 이 풀세트가 빠르단 소리가 절대아니다

 

ㆍ 삽입 삭제는 빠르고, 접근은 느리다

 list<int> li;
 list<int>::iterator itRemember;
 for (int i = 0; i < 100; i++)
 {
     if (i == 50)
     {
         itRemember = li.insert(li.end(), i);
         //지금은 50번째니까 맨뒤에 밀어넣고 그 위치 기억
     }
     else
     {
         li.push_back(i);
     }
 }

ㆍ 처음 데이터를 삽입할때 itRememer과 같이 삭제할 위치를 기억해 두었다? 그럼 erase 자체는 빠르게 일어난다.

li.erase(itRemember);

 

※ 외울 필요 없이 원리를 이해한다면 다 받아들여지는 내용.