[C++] 나만의 DoubleLinkedList(이중연결리스트)만들기 (1) - 기초

연결리스트는 데이터끼리 순서대로 연결된 형식이다.

벡터(vector)의 경우 메모리의 인접한 순서대로 데이터가 존재하지만,

연결리스트는 각 데이터가 메모리에서 인접하지 않더라도 데이터는 다음 데이터의 위치를 저장하고 있다.

 

벡터는 데이터를 중간위치에서 삽입,삭제시 데이터가 밀리거나, 땡겨지게 되는 이슈가 있는데,

연결리스트는 메모리가 인접하지 않아도 되기 때문에 삽입,삭제에서 자유롭다.

단점은 벡터는 인덱스로 데이터에 빠르게 접근할 수 있지만, 연결리스트는 꼭! 순차적으로 검색후 데이터에 접근하게 된다. 그래서 검색의 최후방에 있는 데이터는 가장늦게 찾게 된다.

 

벡터는 중간위치에 삽입,삭제 하려면 인덱스를 알아야 하지만,

연결리스트는 앞 혹은 뒤의 노드를 알아야한다.

 

여기선 어떻게 데이터끼리 위치를 저장하고있는지 알아봐야한다

---

 

1. 단일연결리스트

데이터는 다음데이터의 위치를 저장한다

각 네모아이콘은 데이터를 입력할 수 있는 노드(Node)를 의미하고, 그중 가장 앞에있는 노드를 Head 또는 Header라고 한다.

나는 헤드(Head)에 데이터를 넣지않고 빈 공간으로 표현했지만, 구현에 따라서 헤드에도 데이터를 넣어도 된다. 어차피 헤드도 노드의 종류여서 문제없다.

화살표를 보면 각 노드는 다음 노드를 가리키고 있고, 마지막 노드는 다음 노드가 없기 때문에 아무것도 가리키지 않는다.

단일연결리스트의 이름에서 볼 수 있듯이 한쪽방향으로만 데이터가 연결되어 있다 

3번 노드의 데이터를 가져오려면 헤드 혹은 1번 노드부터 순차적으로 검색한다.

 

1번 노드야 너 3번이니? 아니

2번 노드야 너 3번이니? 아니

3번 노드야 너 3번이니? 응 

...

 

마지막 위치에 데이터를 추가하려면 마지막 노드를 찾아야하는 긴 여정이 필요하다.

그렇기 때문에 맨 앞에 데이터를 추가하는것이 여러모로 이롭다.

 

이미지가 선형적으로 되어 있어 마치 메모리에서도 인접해 보이고 정렬된 느낌이지만 이렇게 표현할 수도 있다

 

노드의 위치는 신경쓰지 않아도 된다.

그저 노드와 노드끼리의 연결만 신경쓰자.

---

2번 노드를 삭제해보자

벡터와 다르게 중간의 데이터를 삭제해도 각 데이터(노드)의 위치는 변하지 않는다

다만 2번 노드를 가리킨 1번 노드는 이제 2번이 아니라 2번의 다음 노드인 3번 노드를 가리키게 된다.

어렵지 않다. 그냥 가리키는것만 신경쓰자!!

 

---

2. 원형연결리스트

마지막 노드는 다시 첫 데이터(노드)를 가리킨다

단일연결리스트는 빈 헤드가 없는것이 기본적이다.

 

단일연결리스트에서 딱 하나 추가된 기능이 있는데

마지막노드가 빈 공간을 가리키지않고 첫 데이터를 가리킨다.

 

나는 원형연결리스트를 써본적이 없어서 그런지... 단일연결리스트보다 좋은 점을 잘 모르겠다.

굳이 따지면 마지막 노드가 nullptr을 가리키지않아 크래쉬가 날 확률이 적어지지만,

무한루프에 빠질수도 있는 단점도 가지고 있다

---

3. 이중연결리스트

모든 노드가 앞뒤로 연결되어 있어 역순환을 할 수 있다.

헤드와 동일한 개념의 테일(Tail)노드가 새로 생긴다.

단일, 원형연결리스트의 단점인 마지막노드검색이 훨씬 수월해진다.

 

단점은 이전 노드를 기억해야하는 변수를 만들고, 테일노드까지 생성해야해서 메모리를 좀 더 쓰게되지만, 

단점에 비해 장점이 크다.

---

나는 이중연결리스트만 구현했고 단일,원형연결리스트는 따로 구현하지 않았기 때문에

이중연결리스트만 소개하겠다.

 

https://github.com/ForestBird1/MyContainer

GitHub - ForestBird1/MyContainer