자료구조(4) 양방향 연결리스트(이중연결리스트) + 머리추가

이름이 의미하듯 노드가 양쪽 방향으로 연결된 구조의 리스트이다. 즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드가 왼쪽 노드를 가리키는 구조다.

 

양방향 연결리스트가 복잡해서 구현하기 부담스러울꺼같지만, 이는 그림상에서 느껴지는 복잡함 때문에 발생 오해이다. 실제로 코드를 비교해보면 상대적으로 더 복잡하지 않음을 알 수 있다. 양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서는 어렵게 구현했던 것이 쉽게 구현되기도 한다. 때문에 오히려 단순하게 느껴지는 측면도 있다.

 

포인터 변수 before의 용도를 기억하는가? 이는 리스트가 한쪽 방향으로만 조회가 가능하기 때문에 유지해야 하는, 삭제의 과정을 위해 유지해야 하는 멤버이다. 하지만 양방향 연결리스트는 양방향으로 얼마든지 조회가 가능하다. 따라서 포인터 변수 before가 불필요하고, before를 유지하기 위해 곳곳에 존재하는 문장들도 불필요하다.

 

총 2가지 형태의 양방향 연결리스트를 구현해보자.

 

1. head->(Null)1 ↔ 2 ↔ 3 ↔ 4(Null)  // head가 Null을 가리키는것이 아니라 1노드의 previous가 Null
2. ㄴㅇㄹ

 

1번은 더미노드 없이 구현하는거라 2번의 더미 노드 모델구현보다 쉽다고 생각한다. 하지만 그 반대이다.

1번의 모델에 적합한 LRmove 함수를 정의하려면, 첫 번째 노드를 삭제하는 경우, 마지막 노드를 삭제하는 경우, 그리고 그 외의 노드를 삭제하는 경우를 각각 별도로 구분해야 하기 때문이다. (...킁… 저자는 그런 이유로인해서인지 LRemove 함수를 구현하지 않고 다른 것들만 가르쳐줬다…단 2번모델의 경우는 전부다 구현했다.)

 

양방향 연결리스트의 구조체 멤버중, 데이터의 조회를 목적으로 선언된 멤버는 cur 하나뿐이다. 즉 단순 연결리스트에(원형리스트) 있었던 before가 존재하지 않는다.

 

조회에 사용되는 멤버 cur는 LFirst 함수가 호출됨과 동시에 초기화되니 별도로 초기화할 필요는없다(원형리스트에서는 다 초기화해줬었는데…? 일단 SKIP)