(3) LinkedList
1. LinkedList
- 배열은 자료구조가 간단하며 사용하기 쉽고 읽어오는데 걸리는 시간이 가장 빠르다는 장점이 있다.
- 그러나 배열은 단점 또한 존재하는데 아래와 같다.
(1) 크기를 변경할 수 없다.
: 변경할 수 없으므로 새로운 배열을 생성해야 한다.
: 또한 크게 생성하면 메모리 낭비가 있다.
(2) 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
: 차례대로 추가하거나 뒤에서 데이터를 삭제하는 것은 빠르지만, 중간에 데이터를 추가한다면, 다른 데이터들을
복사해서 옮겨야 된다.
- 위와 같은 단점들을 보완하기 위해서 링크드 리스트가 등장하게 되었다.
- 배열은 연속적이지만, 링크드 리스트는 불연속적으로 구성되어 있다.
- 위 그림처럼 링크드 리스트는 클래스 안에 2개의 속성을 가져야 한다.
- 추가와 삭제는 주소 노드만 바꾸면 빠르게 변경이 가능하다.
2. 더블 링크드 리스트(이중 연결 리스트)
- 링크드 리스트는 이동방향이 단반향이기 때문에 다음 요소에 접근은 쉽지만 이전 요소에 접근하기 힘들다.
그래서 이를 보완하기 위해 더블 링크드 리스트(이중 연결 리스트)가 등장하게 되었다.
- 그렇다보니, 이중 연결 리스트는 링크드 리스트보다 더 많이 사용하게 되었다.
- 위 그림처럼 이중 연결 리스트는 클래스 안에 3개의 속성을 가져야 한다.
3. 더블 써큘러 링크드 리스트(이중 원형 연결 리스트)
- 더블 써큘러 링크드 리스트는 이중 연결 리스트의 접근성을 보다 향상시키기 위해 등장하게 되었다.
- 차이는 단순하게 첫번째 노드와 마지막 노드의 변화만 있다.
- 실제로 LinkedList 클래스에는 이름과 달리 더블 링크드 리스트로 구현되어 있다.
- LinkedList 역시 List 인터페이스를 구현하였기 때문에 ArrayList와 내부 구현방법만 다를 뿐
제공하는 메서드의 종류와 기능은 거의 같다.
- LinkedList 클래스의 메서드에 대한 상세한 내용은 자바의 정석 598p~599p를 참고하자.
4. 링크드 리스트를 이해하기 위한 예제(1)
: 이번 예제는 ArrayList와 LinkedList 둘 다 순차적 또는 중간에 추가/삭제를 통해 장단점을 보는 예제이다.
( 위의 결과로 순차적으로 추가/삭제하는 것은 ArrayList가 더 빠르다. 그 이유는 데이터의 배열을 재배치할 필요가
없기 때문이다. 그러나 만약 크기 지정을 해주지 않았다면, 새로운 공간을 확보하는 시간 때문에 LinkedList가
더 빠를 수 있다. )
( 위의 결과로 중간에 추가/삭제하는 것은 LinkedList가 더 빠르다. 그 이유는 각 Node간의 연결만 변경해주면 되기
때문이다. 반면에 ArrayList는 중간에서 다시 재배치하고 빈공간을 채워야하기 때문에 느릴 수밖에 없다. )
( 결론은 데이터의 크기가 크다면 장단정을 잘 살펴서 적절한 List를 사용해야 하고, 데이터의 크기가 작다면
사실 어느 것의 list를 사용해도 성능 부분에서는 무의미하다. )
5. 링크드 리스트를 이해하기 위한 예제(2)
: 이번 예제는 ArrayList와 LinkedList 둘 다 접근하는 시간을 통해 비교하는 예제이다.
( 위의 결과로 ArrayList가 LinkedList보다 순차적으로 접근하는 시간이 더 빠르다. )
( LinkedList는 불연속적인 공간에 n번째 데이터를 타고 차례대로 가야지만 찾을 수 있기 때문에 느리다. )
( 일반 배열의 경우는 "배열의 주소 + ( n * 데이터의 타입 크기 )" 를 통해 얻을 수 있다. )
( 예: 0x100 + ( 2번째 인덱스 * 4byte ) = 0x108 )
( 4,5번의 예제를 통해 알 수 있는 점은 다루고자 하는 데이터의 개수가 변하지 않는 경우라면 ArrayList를 쓰는 것이
유리하고, 반대로 변경이 잦다면 LinkedList를 사용하는 것이 유리하다. )
( 또한 두 클래스의 장점을 가지고 조합해서 작업하는 경우도 생각해볼 수 있다. )
