궁금한거?
1. 구조체는 소멸자 없어도 되나??
연결형 리스트 구조 (복습)
우리가 구현한 것은 지금
struct LinkedListNode의 멤버 변수로
LinkedListNode< T > m_prevNodeAddr;
LinkedListNode< T > m_nextNodeAddr;
T
이렇게 가지고 있고
class LinkedList의 멤버 변수로는
LinkedListNode< T > m_headNodeAddr;
LinkedListNode< T > m_tailNodeAddr;
int m_dataCount;
이렇게 가지고 있음.
Linked List Member❗
그러면 class LinkedList inner class로 iterator를 가진다면
iter가 이 연결형 리스트의 두번째를 가르키는 상황일 때
iterator는 어떤 멤버 변수를 가지고 있어야 이것이 가능할까??
headNode의 주소와 인덱스를 안다?
나도 이렇게 생각하긴 했는데 이러면 만약 중간에 있는 데이터에 접근을 할 때 너무 느리다.
첫번째 주소를 알 경우 주소연산으로 몇번 건너 뛰어서 접근 가능한것은
연속적인 메모리 주소(구조)를 가진 "배열"에서 좋은것임
그런데 List는 메모리 주소가 연속적이지 않다.
(동적으로 메모리를 (힙에) 할당해서 그곳을 노드로 서로 연결 시키기 때문에)
=> 아하 씨발 이거 Dictionary 쓰면 될거같은데?
그러면 O(n)이다. (1번 수행)
iterator 멤버 구현
-
누구의 리스트인 지 확인 하기 위한 리스트의 주소
-
노드의 주소를 알기 위한 노드 주소
이렇게 일단 멤버로 가지고 있어보도록 하자.
유효성 체크할 수도 있으니 bool변수 추가.
참고로 < T > 이거는 정확하게 하기 위함이다.
없어도 무방함 -> 왜? => inner class라서 T가 어떤것인지 이미 알고 있기 때문에. ㅇㅋ?
iterator 생성자, 소멸자 👍
생성자는 오버로딩을 통해 두가지 만들어준다.
음음...
소멸자 부분에 아무것도 없는데
iterator는 리스트의 데이터를 가르키는 역할이라
직접적으로 리스트의 데이터를 삭제 하면 안된다.
왜? =>
또 한 가지 특징으로 List 에는 반복자(iterator) 라는 개념이 있습니다. 연결 리스트를 탐색할 때 사용하는 포인터와 비슷한 개념으로 List 에 저장된 데이터에 접근하기 위하여 사용되며 컨테이너에서 특정 위치를 가리키며 포인터와 비슷하게 ++ 와 -- 와 이동합니다.
즉 iterator는 다시 말하지만 "반복자"이고, 데이터를 "탐색" 할 때, 데이터에 "접근" 하기 위하여 사용이 된다.
그래서 리스트의 데이터를 직접적으로 뭔가를 삭제하면 안된다.
iterator의 operator 구현
이 iterator가 가르키는 대상으로 "역참조"하여 접근하는 연산자가 있어야 할 것이다.
역참조해서 direct로 수정할 수 도 있기 때문에
T& 로 주어야한다.
linkedList 함수
begin의 경우 return 값으로 iterator를 던져주는데
인자를 두개를 넣어주는 생성자로 반환을 해준다.
어떤 LinkedList인지 this로 주고, 시작을 반환하는 함수begin이니까 headNode의 주소를 준다.
어떤 경우 end iterator이냐? ❗❗
nullptr인 경우 end iterator라고 간주를 한다.
LinkedList안에 있는 데이터(m_dataAddr이)가 실제로 있는지 없는지는 모르지만,
어쨋거나 내가 LinkedList를 알고(주소를 알고), 현재 가르키고 있는 ListNodeAddr(노드 포인터가) null이야!
리스트가 관리하고 있는 데이터들 중에 "특정 노드"를 가르키는 역할을 하는게 iterator이다.
그런데 iterator가 nullptr이다. => 그러면 end iterator 라고 간주를 한다.
따라서 이렇게 반환을 해주도록 하자.
테스트
이렇게 100이 출력이 가능함.
또한 operator * 는 반환형이 참조라서 값수정이 가능함.
이렇게
처음에 100이였다가 123으로 바뀜.
operator 추가 구현
- ++
-
!=
-
==
이런거 추가해야함.
!(this == other) 가 아니라
!(*this == other) 인 이유
그냥 this하면 주소값이라서...
!=, ==
vector를 했을때 와 비슷.
후위, 전위
후위에서
차이점은 후위에서는 복사본을 던져주어야 하기 때문에
반환이 iterator이고, 인자로 int라는 것은 후위라는 것을 명시해주기 위해서이다.
그리고 75번째줄 iterator copyIter(*this); 는
*this 자체를 넘겨준 것임.
즉 "복사 생성자"를 통해 copyIter에 this자체를 복사해서 바로 "생성"한 것임.
복사생성자 👍
이 "복사 생성자"는 내가 구현해놓지 않으면 자동으로 구현될 녀석이다.
for문 테스트 ❗🛫
지금 이렇게 for문 돌렸었는데
에러남! 이유가 뭐냐하면은 어제 내가 햇갈려 했던 '.', '->' 이다.
. , -> ❗❗❗
지금 이부분인데
https://velog.io/@starkshn/CPP%EC%96%B4%EC%86%8C66erase-2#2----%EC%B0%A8%EC%9D%B4%EC%A0%90
일단 쉽게 정리하면 객체는 . 사용, 포인터 변수는 -> 사용이다.
그래서 지금 other를 보면
myList의 end인데 end의 반환 형식이 LinkedList< T >::iterator 이다.
iterator는 복사생사인 녀석을 반환을 하는데
이녀석을 생성해서 반환을 한다.
이것도 하나의 객체이기 때문에 포인터 변수에 사용을 하는 '->' 이 아니라 '.'을 사용해야한다.
erase, insert
이거 두개 구현 해야한다.
insert 기능 잠깐 보기
이렇게하면 100 앞에 200이 들어감
insert반환타입이 ieterator인데 들어갔던 iterator를 가르키는 것을 반환한다.
100 200 사이에 넣을려면
이렇게 ++ 해주고 데이터 삽입 ㄱㄱ
insert함수 ❗❗❗
insertIter.m_i_listNode->m_nextNode를 updateNode로 열어주고
insertIter가(인자로 온 녀석)이 가르키고 있는 이전 node는 새로운 노드와 연결시켜주어야한다.
이부분 잘 보면서 분석해봐라.
딱하나 예외 처리
insert하려는 부분이 headNode일 경우
이녀석을 호출한 녀석은 list이기 때문에 포인터 변수 this의 -> 로 접근을한 headNodeAddr과 비교를 해준다.
헤드일 경우와 아닐 경우
insert가 가장 첫번째라면
헤드를 옮겨야 하니까
새로 만든 노드와 연결을 해주는 작업이다.
이부분 잘 이해가 안간다면 계속 보면서 생각하도록 하자.
서로 연결해주는 거 밖에 없음.
