[Java] LinkedList가 과거에는 doubly circular linked list?

 

저자가 운영하는 카페에 질문이 올라왔다.

3판 / 598페이지 / 내용 중 "실제로 LinkedLIst클래스는 이름과 달리 링크드 리스트가 아닌 더블 써큘러 링크드 리스트로 구현..."

요지는 책에는 LinkedList의 구현이 더블 순환 연결리스트로 구현이 되어 있다고 되어 있는데, 본인이 코드를 짜보니 아닌 것 같다는 질문이다.

그런데, 자바의 정석 3판에 인쇄본에 따라 내용이 다르게 되어 있는 것 같다.

질문자의 사진은 아래와 같다.

내가 가지고 있는 3판은 아래와 같다.

진실은?

Java SE 11 버전의 Java Doc을 보면 아래와 같이 되어 있다.

다시말해 이중 연결리스트로 구현이 되어 있다는 것이다.

LinkedList라는 클래스는 1.2부터 추가가 되었다.

1.2 버전은?

JDK1.2의 Java Doc에는 별도로 구현에 대해 명시하지 않았다.

결국 소스코드를 확인해봐야 했다.

JDK 1.2.2 update 17 설치

다행히 구 버전에 대한 인스톨러를 제공하고 있다.

mac os 용은 없어서 윈도우에 설치를 했다.

오랫만에 보는 옛날 로고.

인스톨러도 오래전 인터페이스다. 윈도우7에 설치를 했는데 설치가 된다니 오히려 신기했다.

Java 2 SDK, SE v1.1.2 update 017을 설치

설치가 되면 src.jar 를  찾는다.

압축을 푸는 것은 아래의 명령을 이용한다.

jar xf src.jar

java.util 디렉터리에 LinkedList.java 파일이 있다.

열어보면 Effective Java로 유명한 Josh Bloch 가 2001년 11월 29일 만들었다고 주석에 써있다.

위의 코드가 빈 리스트를 만드는 코드인데, 헤더의 다음과, 이전과 헤더는 같도록 설정이 되어 있다.

next와 previous를 저장하는 것으로 보아 전형적인 double linked list임을 알 수 있다.

 

사실 Circular double linked list를 구현했다면 리스트의 순회가 불가능했을 것이다.

왜냐하면 무한루프에 빠질 수 밖에 없기 때문이다. 마지막 원소에 접근하고 다음원소는 다시 처음 원소가 될테니 말이다.

 

Iterator의 구현을 보면 명백하다.

다음 원소가 있는지 확인할 수 있는 hasNext()에서 다음 인덱스가 리스트의 크기와 같으면 boolean을 반환하기 때문이다.

순환 이중 연결리스트였으면 hasNext()는 원소가 비어있지 않는 이상 항상 true를 반환해야 한다.

 

원소를 반환하는 next() 역시 다음 인덱스가 size와 같아지면 (즉 마지막 원소를 이미 반환했으면) NoSuchElementException을 던지고 있다.

 

결론

JDK 1.2부터 LinkedList는 원래부터 이중 연결리스트였다.

 

혹시나 해서 1.4 버전도 확인

저자님이 댓글을 아래와 같이 달아주셨다.

1.4버전도 아직 다운을 받을 수 있었다.

배너 로고가 바뀌었다.

인스톨쉴드를 사용하고 있다.

이번에는 윈도우라서 그런지 jar가 아닌 zip 파일로 압축했다.

1.46 소스

여전히 저자가 Josh Bloch로 되어 있고 날짜는 2003년 1월 24일이다.

1.2와 비교를 하기 위해 diff를 했다.

크게 바뀐 것은 없다. 주석에 대한 수정과 사소한 변화들..

딱히 Circular로 바뀌지 않았다.