Java LinkedList, LinkedList vs ArrayList

※ LinkedList를 공부하기 전 다시 한 번 배열의 장단점을 보고 시작하자!

장점

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

단점

• 크기를 변경할 수 없다.

• 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야한다.
  ⇒ 즉 기존의 연결된 주소를 끊고 새로운 주소를 입력해준다.
  ⇒ 더 큰 배열을 생성하고 → 복사 → 참조변경
• 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨

• 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 한다.
그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

 

LinkedList

• 배열의 단점인 크기 변경 불가, 추가 삭제 시간을 보완할려고 나온것이 LinkedList이다.
• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)한다. 

데이터 삭제 - 단 한 번의 참조변경만으로 가능하다.

데이터 추가 - 한 번의 Node객체 생성과 두 번의 참조 변경만으로 가능

위에 이미지에서 그림을 나란히 놓은것뿐, 오른쪽 핑크그림처럼 연결되어있는 형태이다.

 

 

LinkedList 종류 및 특징

• 링크드리스트(Linked List) :
  연결리스트, 데이터 접근성이 나쁨(단점)
  ex) 첫 번째 요소는 두 번째 요소의 위치만 알지 예를들어 3번째 5번째 요소의 위치는 모르기때문에 5번째 요소를 알고싶다면 2번째 3번째 4번째 요소를 거쳐 알 수 있다.
• 더블리 링크드 리스트(Doubly Linked List) :
  이중 연결리스트, 접근성 향상, 링크드리스트의 단점을 개선 부분
• 더블리 써큘러 링크드 리스트(Doubly circular Linked List) :
  이중 원형 연결리스트

 

ArrayList vs LinkedList - 성능 비교

• 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름
• 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
• 접근시간(access time) - ArrayList가 빠름

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