Whiteship's Note

'ArrayList'에 해당되는 글 1건

  1. 2006.12.22 LinkedList vs ArrayList (6)

LinkedList vs ArrayList

Java : 2006.12.22 00:05


Agile Java 번역본 p467 두 번째 단락이 끝나는 지점에서 이런 문구가 있습니다.

"리스트의 끝이 아닌 부분에서 제거와 추가가 반복되는 콜렉션에 대해서는 링크드 리스트가 ArrayList보다 나은 성능을 보인다."

ArrayList와 LinkedList의 특성 때문에 그렇다고 짐작이 됩니다. ArrayList의 경우에는 배열을 기반으로 만들어진 자료구조이고 LinkedList는 현재 자신이 가지고 있는 값과 다음 노드를 가리키고 있는 변수를 가진 노드로 구성되어있는 자료구조 입니다.

따라서 ArrayList의 경우 배열의 특징인 인덱스를 사용하여 각각의 값에 바로 접근 할 수 있는 반면에 LinkedList는 맨 첫 노드 부터 원하는 위치 만큼 이동한 뒤에 값에 접근 할 수 있다는 단점이 있습니다.

대신 LinkedList는 책에서 언급한 대로 중간에 끼워 넣을 때 다음 노드를 참조하는 변수만 바꾸는 간단한 작업만 하면 되지만 ArrayList는 중간에 끼워 넣으려면 끼워 넣고 싶은 위치 다음에 있는 자료들을 한칸씩 쭉~ 미뤄야 하는 단점이 있습니다.

결국 그때 그때 다르다는 결론이 날 것 같아서 표를 찾아봤습니다.
사용자 삽입 이미지
빅O 노테이션[각주:1]으로 ArrayList와 LinkedList의 효율성을 나타낸 표입니다.
ArrayList의 경우 최악의 경우에서도 효율성이 O(1)[각주:2]을 나타내는 operation들이 3개나[각주:3] 됩니다. 하지만 LinkedList의 경우에는 하나도 없는 셈이나 마찬가지입니다.

이유는...첫 번째 노드 부터 차근차근 찾아 들어가야 한다는 것 때문입니다. 중간에 끼워 넣으려고 해도 결국 첫 번째 노드 부터 원하는 위치 까지 찾아 가야 하기 때문에 찾고자 하는 위치가 만약 List의 거의 마지막에 위치해 있다면 길이가 n인 List에서의 효율성이 n에 비례해서 커지기 때문입니다.

그래도 경우의 수를 따졌을 때 종단에 문언가를 추가할 확률이 그렇치 않을 확률에 비해 낮기 때문에 책에서는 이렇게 얘기를 하고 있는것 같습니다. 빅O는 어디까지나 최악의 경우이니깐요.
  1. 최악의 상황에서의 효율성을 최대한 단순화 시켜서 나타내는 표시법 [본문으로]
  2. 어떠한 경우에서도 고정된 수의 연산이 발생하는 가장 이상적인 효율성 [본문으로]
  3. 맨 아래 메소드들은 제외합니다. [본문으로]

'Java' 카테고리의 다른 글

Generic과 다형성 2탄  (4) 2007.01.05
Generic과 다형성  (0) 2007.01.05
자바 검은 띠에 도전해 보시길~  (2) 2006.12.31
Hiding Method  (0) 2006.12.31
Overriding - covariant return type  (6) 2006.12.31
LinkedList vs ArrayList  (6) 2006.12.22
Agile Java 소스코드(10장까지..)  (8) 2006.12.21
Reflection  (0) 2006.12.19
... 가변인수(varargs)  (2) 2006.12.11
for each 구문 사용법  (0) 2006.12.11
JUnit Reloaded  (0) 2006.12.07
top

  1. Favicon of http://chanwook.tistory.com/ BlogIcon 찬욱 2006.12.22 07:58 PERM. MOD/DEL REPLY

    재미있었던 자료구조 시간이군요..ㅋㅋ
    저 눈에 익숙한 표..큭

    Favicon of https://whiteship.tistory.com BlogIcon 기선 2006.12.22 09:29 신고 PERM MOD/DEL

    ㅋㅋ두통은 좀 괜찮아?
    트리도 어서 써드려야 할텐데 이젠 지친다.

    Favicon of http://chanwook.tistory.com BlogIcon 찬욱 2006.12.22 11:13 신고 PERM MOD/DEL

    흠..그쵸..피드백 없는 일이 얼마나 힘든지 느끼는 순간입니다. 그래도 형 화이팅!!!!(떠 넘기는 모드 -_-;;)

    두통은 아직 매우 많이 안 좋습니다..ㅋ

    그리고 저 1월 첫 주까지 일 연장 될 듯한 분위기에요..ㅋ
    여기서 부탁하는데..빠지기도 미안하고해서요...푸크

    Favicon of http://whiteship.tistory.com/ BlogIcon 기선 2006.12.22 23:14 PERM MOD/DEL

    건강이 우선이지. 근육좀 많다고 방심하지말고 건강 잘 챙겨.

    몇일 전 내가 진짜 행복한 사람이라고 느꼈던 적이 있었지. 그날은 갑자기 몸이 안좋아져서 집에가서 12시간을 내리 잠을 잔 날인데..

    내가 아플때 이렇게 쉴 수 있고 공부하고 싶을 때 할 수 있는 것이 얼마나 행복한건지 알 수 있더군.

  2. Favicon of http://chanwook.tistory.com BlogIcon 찬욱 2006.12.23 21:18 신고 PERM. MOD/DEL REPLY

    ㅋㅋ 태어나서 처음으로 두통약이란 걸 먹었는데요..
    머리가 그 저도로 아플수도 있겠구나 싶더군요..

    좋으시겠어요..저도 따뜻한 집이 그립습니다 ~ ~ 아아~~

    Favicon of https://whiteship.tistory.com BlogIcon 기선 2006.12.23 22:01 신고 PERM MOD/DEL

    ㅇㅇ좋더군.
    나도 몇 주 전까지 두통이 생겼었는데 갑자기 추워져서 그런가봐;

Write a comment.