개념 - 싱글 링크드 리스트

싱글 링크드 리스트의 사용법이나 개념 자체는 단순하지만, 구현시에는 다음과 같은 유의점이 존재한다.

여러번의 삽질 결과로 얻은 교훈이지만, 경험에서 단편적으로 깨달은 것이라 틀린 내용이 있을 수도 있다.

1. 헤드 더미

헤드 더미를 두지 않고 구현시 첫 노드와 관련된 일을 할 때마다 헤드도 염두에 둬야 한다. 

만약 더미가 없다면 헤드에 삽입을 할 때 헤드의 앞에 연결해야 할까 뒤에 연결해야 할까? 뒤에 연결할경우 아무리 삽입을 해도 헤드 노드는 영원히 자리가 고정이다. 앞에다 연결할 경우 입력한 순의 역순으로 연결되며 헤드도 바꿔줘야 한다.

만약 삽입한 데이터를 지우고 싶다고 해보자. 더미가 없을 때 헤드 노드를 지우려면 반드시 현재 인덱스부터 지워나가야 한다. 그런데 그렇게 헤드를 지웠다고 쳐도 같은 방법으로 다른 노드를 삭제하기 위해선 이전 노드의 정보가 필요하다. prev라는 변수를 만들어서 이전 노드의 정보를 다루려면 이제 신경써서 관리해야할 것이 또 느는 것이다. 헤드 더미를 안둬서 더 많은 일이 강요되고있다.

더미를 두지 않았을 때의 이점은 더미 용량밖에 없는듯 하니 그냥 더미를 두자.

2. 이전 노드 정보

위에서 말했지만 만약 순회중에 어떤 노드를 '바로'삭제하기위해서, 따로 변수를 두어 거쳐온 노드(prev)을 저장하게끔 하면 이를 계속해서 추적해야한다. 만약 여기다 tail도 사용한다면 prev를 더 신경써서 구현해야 한다. 제한적인 기능이라면 상관없지만, tail이나 prev를 사용하지 않을수록 코드가 읽기 쉽고 버그가 날 확률이 줄어들 것이다.  tail이나 prev가 절실한 상황이면 이중 연결 리스트가 나을 것이다.

3. insert와 insert_after, erase와 erase_after

보통의 insert는 자기 위치에 새 데이터를 넣고 자기는 뒤로 한칸 밀려난다. 그런데 이런 방식으로는 싱글 리스트에선 insert로 맨 끝에 새 노드를 삽입할 수가 없다. 따라서 tail을 관리해서 push_back을 만들던지, insert_after로 자기 뒤에다 삽입하게 하던지 선택해야 한다. 비슷한 의미로 erase는 자기를 지우고 뒤의 노드를 반환한다. 따라서 리스트가 안끊어지려면 자기 이전의 원소를 저장해놔야한다. erase_after는 (헤드 더미가 있다는 전제하에) 이런 문제가 없다.

4. STL 스타일 std::forward_list

insert_after와 erase_after를 사용하고 , 또 tail 변수를 두지 않아 이를 관리할 필요가 없고 push_back도 없다. 원소 접근도 없고 Advance와 ++(next)로 노드를 순회한다. 헤드 더미를 가리키는 before_begin()을 제공한다. 참조 : http://en.cppreference.com/w/cpp/container/forward_list

싱글 링크드 리스트에 대해서 알아보았다. 생각보다 고려해야 할 것이 많다.

누군가 싱글 링크드 리스트를 구현해보라고 한다면 4번을 떠올려야겠다는 생각이 드는 하루다.

헤드 더미와 prev, tail을 두는 버전 구현해보기 : http://kid5.tistory.com/251?category=740150

insert_after, erase_after 버전 구현해보기: http://kid5.tistory.com/252

추가 : std::forward_list 정보 (출처 : http://www.cplusplus.com/reference/forward_list/forward_list/?kw=forward_list)

Modifiers

assign

Assign content (public member function )

emplace_front

Construct and insert element at beginning (public member function )

push_front

Insert element at beginning (public member function )

pop_front

Delete first element (public member function )

emplace_after

Construct and insert element (public member function )

insert_after

Insert elements (public member function )

erase_after

Erase elements (public member function )

swap

Swap content (public member function )

resize

Change size (public member function )

clear

Clear content (public member function )