50. Java LinkedList

1. 배열의 장단점

  1) 배열의 장점 : 구조가 간단하고, 데이터를 읽는데 걸리는 시간(접근시간)이 짧다.

  2) 배열의 단점

    ① 배열의 크기를 변경할 수 없다. 크기를 변경하는 경우 새로운 배열을 생성 후 데이터를 복사해야 한다.(참조변경) 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리 낭비가 발생할 수 있다.

    ② 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.(배열 중간에 데이터를 넣거나 삭제) 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

 

2. LinkedList

  1) 배열의 단점을 보완하기 위해 나왔다.

  2) 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)한다.

  3) 노드라는 공간에 데이터를 저장하고, 다음 노드의 위치를 같이 저장한다.

  4) 따라서 단 한 번의 참조변경만으로 데이터를 조회하고 다음 데이터를 조회 또는 삭제할 수 있다.

  5) 데이터 삭제 : 단 한 번의 참조변경으로 처리가 가능하다.(앞 뒤의 노드를 서로 연결해준 뒤 삭제하는 데이터가 있는 노드를 지우면 된다.)

  6) 데이터 추가 : 한 번의 Node 객체 생성과 두 번의 참조 변경만으로 가능하다.(노드 생성 후 앞의 노드에 생성된 노드 주소 추가, 생성된 노드에 다음 노드 주소 추가)

 

3. LinkedList 단점

  1) 링크드 리스트(linked list)는 연결 리스트이기 때문에 데이터 접근성이 나쁘다. 즉, 특정 노드를 찾으려면 반드시 다음 노드를 거쳐서 찾아야 한다. 또한 다음 노드의 위치만 알기 때문에 되돌아갈 수 없다.

  2) 단점을 개선하기 위해 나온게 더블리 링크드 리스트다.(doubly linked list)

  3) 더블리 링크드 리스트는 이중 연결리스트로서 접근성을 향상시켰다.(즉, 다음 노드의 위치 정보와 내 앞의 노드 정보도 알 수 있다.) 자바는 이중 연결리스트로 구현이 되어 있다.

  4) 더블리 써큘러 링크드 리스트(doubly circular linked list) : 이중 원형 연결리스트로서 첫 번째 노드와 마지막 노드의 주소값을 서로 연결한 것이다. 따라서 순환하는 구조다.

 

4. ArrayList vs LinkedList

  1) 순차적으로 추가/삭제: ArrayList가 빠르다.

  2) 비순차적으로 추가/삭제 : LinkedList가 빠르다.

  3) 접근시간 속도 비교 : ArrayList가 빠르다. 

  4) 결론 

    ① 읽기 속도 : ArrayList

    ② 추가/삭제 : LinkedList