0x04강-연결리스트

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함

배열과 다르게 공간에 연속적으로 원소들이 위치를 가지고 있지 않기 때문에

 

2.임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)

 

3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만, 할당이 다소 쉽다. 

 

 

STL에 있는 list는 이중 연결 리스트이다. 

 

배열과 연결리스트의 비교

 

연결 리스트의 경우 주소값을 가지고 있어야 하기 때문에

32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N바이트가 추가로 필요하고, 64비트 컴퓨터라면

주소값이 64비트(=8바이트)이니 8N바이트가 추가로 필요하게 된다. 

 

임의의 위치에 원소를 추가하거나 제거해야 하는 상황이 많을 경우에는 연결 리스트의 사용을 고려해볼 수 있다. 

연결 리스트의 정석적인 구현은 NODE  구조체나 클래스를 만들어서 원소가 생성될때 동적할당을 하는 방식. 

 

코딩테스트 에서는 STL list를 사용하면 된다. STL list가 Doubly Linked List 구조를 가지고 있기 때문에 연결 리스트가

필요하면 그냥 가져다가 쓰면 된다. 

STL list를 사용할 수 없는 상황에서 사용할만한 야매 연결 리스트

이전 다음 원소의 포인터 대신 배열상의 인덱스를 저장하는 방식으로 구현한 연결리스트. 

pre나 nxt의 값이 -1이면 이전, 다음 원소가 존재하지 않는다는 의미. 

unused는 현재 사용되지 않는 인덱스, 즉 새로운 원소가 들어갈 수 있는 인덱스이고, 

원소가 추가된 이후에는 1씩 증가될것. 

특별히 0번지는 연결 리스트의 시작 원소로 고정

달리 말하면 0번지는 값이 들어가지 않고 단지 시작점을 나타내기 위한 dummy node.

 

STL list에 대해서 익숙해져야 하는데, 여기서 사용하는 iterator라는것은 반복자 라고 하고, 어떤 컨테이너를 사용하든 일관적이게 원소에 접근할 수 있게 사용되는것이 반복자 라는 원소 접근 방법이라고 보여진다. 

그에 관한 자세한 사항은 학습에 도움이 되는 블로그 글을 추가적으로 첨부하고 이 글을 다시 복습할때마다 

가서 학습해보도록 하자. 

https://spenshi.tistory.com/entry/C-%EB%B0%98%EB%B3%B5%EC%9E%90iterator

C++ 반복자(iterator), vector와 list의 반복자 비교

 

반복자에 *연산자를 붙여서 내부의 원소에 접근하여서 출력 등을 할 수 있다. 

https://velog.io/@dnflrhkddyd/C%EB%AC%B8%EB%B2%95-%EB%B0%98%EB%B3%B5%EC%9E%90-Iteratorvector-list

[C++문법] 반복자 Iterator(vector, list)

 

역참조 라는 것인데 

http://andyader.blogspot.com/2013/08/c-c.html

C, C++의 연산자 * 와 & 의 기능에 관하여

 

이 블로그 글을 보면 설명이 되어 있으니 참고하도록 하자. 

 

 

List와 iterator 관련된 구현에서 

iterator를 신경써서 보아야 할 부분은 

List.end()-> 끝 원소의 그 다음번을 가리킨다

t=L.erase(t); 같은 절차, 

그리고 erase는 제거한뒤에 그 다음 원소의 위치를 반환한다는것, 

그리고 L.insert(t,6) 같은 절차는

t가 가르키는 위치 앞에 6을 삽입.

등등, 

iterator가 어디를 가리키는지, erase와 end, insert등이 어디를 가르키고 어디에 어떤 과정을 거치는지 등을

헷갈리지 않고 정확하게 기억하고 있어야 한다. 

이걸 제대로 알지 못하면 iterator를 활용해서 원하는 위치의 원소에 접근하지 못한다.