LinkedList

배열의 장단점

• 장점

1. 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근 시간, access time)이 짧음

• 단점

1. 크기를 변경할 수 없음

   • 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함
   • 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면 메모리가 낭비됨

2. 비순차적인(데이터의 추가, 삭제)에 시간이 많이 걸림

   • 데이터를 추가하거나 삭제하기 위해 다른 데이터를 옮겨야 함
     • 순차적인 데이터 추가(끝부터 추가)와 삭제(끝부터 삭제)는 빠름

크기 변경 안 되는 것과 추가 삭제 시간이 느리다는 단점을 보안하는 LinkedList

LinkedList

• 배열의 단점을 보완
  • 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link) : 각 요소가 연속적임

1. 데이터의 삭제 : 단 한 번의 참조변경만으로 가능

   개별적인 노드(요소)들이 연속적으로 존재하므로 다음 노드가 무엇인지에 찾아갈 수 있는 참조변수를 갖고 있음

2. 데이터의 추가 : 한 번의 node 객체 생성과 두 번의 참조 변경만으로 가능

LinkedList - 이중 연결 리스트

• 링크드 리스트 : 연결리스트, 데이터 접근성이 나쁨

• 더블리 링크드 리스트(doubly linked list) : 이중 연결 리스트 > 다음 노드와 이전 노드가 무엇인지 찾아갈 수 있는 참조변들을 갖고 있어서 링크드 리스트보다 접근성 향상

• 더블리 써클러 링크드 리스트(doubly circular linked list) : 이중 원형 연결 리스트 > 더블리링크드리스트 + 마지막 요소를 맨 처음 요소와 연결하고 맨 처음 요소를 마지막 요소와 연결함

ArrayList와 LinkedList 성능 비교

• 순차적으로 추가/삭제
  • ArrayList : 데이터 이동이 없고 한번에 저장 공간을 추가해주므로 더 빠름
  • LinkedList : 객체를 만들고 연결하므로 더 느림
• 비순차적으로 데이터 추가/ 삭제(중간 추가 삭제)
  • LinkedList가 더 빠름
• 접근 시간
  - ArrayList가 빠름

  인덱스가 n인 데이터 주소 = 배열의 주소 + n *데이터타입의 크기

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가 삭제는 더 빠름 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

---

☃참고❄
자바의정석-LinkedList