자바의 연결리스트(LinkedList)

오늘은 컬렉션 중에서도 자바의 연결리스트인 LinkedList에 대해서 공부하는 시간을 가져보기로 하겠다. 연결리스트 즉 링크리스트(LinkedList)는 큐(Queue)의 기능을 활용한 클래스 중에서 가장 많이 쓰이는 클래스로서 리스트(List)의 기능도 구현하고 있으므로 다목적으로 사용이 가능하다. 컬렉션에서 ArrayList가 LinkedList에 비해서 훨씬 많이 쓰이긴 하나 프로그램에서 요소들의 잦은 삽입이나 삭제를 반복하는 경우가 빈번하게 발생한다면 프로그램의 효율성을 위해 연결리스트를 사용하는 것에 대해 고려해볼만 하다.^^

위의 그림은 LinkedList의 구조에 대해서 표현한 것이다. Queue에 대해서 조금 아는 이들이라면 쉽게 이해가 될것인데 설명하자면 연결리스트의 head 부분은 당연히 첫번째 요소를 뜻하는 것이고 tail은 맨 마지막 요소를 뜻한다. 각 요소가 다음 요소와 링크로 연결되어 있으며 맨 마지막 요소의 링크는 그림처럼 아무것도 없는 허공(?null)을 지정하고 있다고 생각하면 이해가 쉬울 것이다.^^

이렇게 링크로 연결되어 있는 연결리스트가 잦은 삽입시 배열리스트에 비해서 왜 효율적인지 지금부터 설명하겠다. 배열리스트의 경우에 요소를 삽입한다면 삽입한 그 자리 이후에 위치한 요소들은 전부 뒤로 한칸씩 밀어야한다. 삽입하는 자리가 거의 뒤쪽이라면 별 지장이 없겠지만 요소들이 많은데 거의 처음에 요소를 넣어야하는 상황이 발생할 경우 시스템에 엄청나게 부하(?)가 걸릴수 있다. 그건 요소를 삭제하는 경우에도 마찬가지일 것이다. 그때는 반대로 그 뒤의 요소들을 모두 한칸씩 앞으로 보내야하니까 말이다.ㅎㅎ 그에 반해 연결리스트를 사용할 경우 요소를 넣을 위치에 다음 요소를 가리키는 링크의 위치만 변경하면 다른 부가작업이 필요가 없다. 말로 표현하는 것보다 그림을 보면 훨씬 간단하니 아래를 보기 바란다.^^

37이라는 새로운 요소를 12와 99 사이에 넣으려는 예제인데 그림에서 보는 것처럼 12의 링크를 새로 넣으려는 요소 37에 지정하고 새로운 요소 37의 링크는 12 다음에 있던 요소 99로 지정하면 요소의 삽입과정이 간단하게 끝난다.

위는 반대로 중간에 있는 요소인 99를 삭제하는 과정이다. 이건 그림에서 보는 것처럼 단지 이전의 요소가 가리키고 있던 링크를 삭제하려는 요소를 건너뛰어 다음의 요소에 링크만 걸어주면 삭제과정이 끝난다. 물론 나머지 링크는 그대로 유지된다.^^

보다시피 연결리스트가 이러하므로 수시로 요소들을 추가거나 삭제한다면 연결리스트가 훨(?) 나을수도 있다. 그럼 연결리스트의 작동원리는 이 정도로 하고 이제 예제를 보기로 하자. 이번 예제는 Queue에 포커스를 맞추어서 내용을 구성하였다. 어차피 이전강의들에서 리스트에 관계된 대부분의 메소드들은 공부하였으므로 큐에 대해서 건드려 보도록 하겠다. 연결리스트(LinkedList)가 큐(Queue)를 구현한 대표적인 클래스이니까 말이다.^^

예제는 아주 심플하면서도 심오(?)하다. 이런걸 한마디로 표현하자면 누워서 떡먹기인데 결과는 아래와 같다.^^

[A]
[A, B]
[A, B, C]
[A, B, C, D]
[A, B, C, D, E]
=== 강이의 JAVA강좌 ===
[A, B, C, D, E, A]
B
[B, C, D, E, A, B]
C
[C, D, E, A, B, C]
D
[D, E, A, B, C, D]
E
[E, A, B, C, D, E]
A
=== 강이의 자바강좌 ===
[A, B, C, D, E]
[A, B, C, D, E]

특별히 어려운건 없을 것이나 위아래 표식이 있는 강이의 자바강좌 사이에 있는 결과값들에 의문을 표하는 이들이 조금 있을지도 몰라 혹시나 정말 혹시나 해서 해석을 곁들이니 이해가 잘 안갔던 이들은 함께 하기 바란다.ㅎㅎ

일단 연결리스트에 A, B, C, D, E 알파벳을 차례대로 넣어서 연결리스트를 만들었다. 초반에 언급했지만 연결리스트 또한 리스트를 계승하므로 add( ) 메소드를 자유롭게 쓸수 있다. 그럼 오늘 예제의 하이라이트(?)인 두번째 for 구문을 살펴보자.

일단 아까처럼 요소 A를 add( ) 메소드를 통해 집어넣으니 결과처럼 연결리스트 맨 뒤에 A가 추가된다. 다음에 어째서 B가 출력되느냐인데 메소드가 하는 기능을 제대로 알면 금새 이해가 될것이다. poll( ) 메소드를 썼는데 이것의 뜻이 개표 또는 여론조사할때 쓰는 표현이다. 개표라는 말의 의미자체가 투표함에서 표를 꺼내서 열어본다는 것이니 연결리스트가 투표함이고 표가 요소라고 가정할 경우 요소를 꺼내서 열어보니 당연히 연결리스트에서는 더이상 꺼낸 그 표, 즉 요소가 없을 것이다. 그런데 poll( )의 메소드는 연결리스트 맨 앞의 요소 헤드, 즉 맨 처음 넣었던 요소를 끄집어내고 그 요소는 없애버린다. 따라서 poll( ) 메소드를 실행한 후의 연결리스트는 [B, C, D, E, A]가 될것이다.ㅎㅎ

그 다음 peek( ) 메소드를 실행하고 출력하라고 했는데 peek의 뜻이 무언가를 엿보다 혹은 훔쳐보다라는 뜻이다. 즉 보기는 보지만 말그대로 그 요소를 삭제하거나 하는 행동은 취하지 않는다. peek( ) 메소드도 poll( )과 마찬가지로 맨 앞의 head 요소를 사용한다. 현재 연결리스트가 A를 끄집어낸 후이므로 가장 앞의 위치한 요소 B를 출력하게 되는 것이다. 이런 식으로 계속해서 반복되는게 두번째 for 구문이다.^^

마지막으로 clone( ) 메소드로 연결리스트를 복사하는 것인데 clone( ) 메소드가 돌려주는 리턴값이 Object라서 연결리스트로 바꿔주느라 캐스팅을 사용한 것이다. 물론 예제처럼 연결리스트로 복사해서 다시 쓸 필요없을 경우 원래의 리턴값인 Object로 받아서 써도 된다. 그렇게 하려면 주석처리한 부분으로 현재의 코드를 수정하면 될것이다.ㅎㅎ

짧게나마 연결리스트(LinkedList)에 대해서 공부해보는 시간을 가져보았다. 이밖에 여러 기능들이 있지만 그건 여러분이 조금만 응용해서 코딩해보면 쉽사리 습득하게 될것이다. 자바 라이브러리(API)는 자바의 바이블같은 존재이다. 내용이 방대하므로 전부다 실험은 못해보더라도 최소한 의문이 생기는 부분들에 대해서만이라도 여러분이 찾아보고 알아보는 정성을 쏟기 바라면서 오늘 강의는 이정도로 하겠다.^^