LinkedList

LinkedList(배열기반)장단점

• 장점
  • 배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간이 짧음
• 단점
  • 크기를 변경할 수 없음
    • 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함
    • 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비
  • 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸림
    • 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함
    • 순차적인 데이터추가와 삭제는 빠름

LinkedList는 배열의 단점을 보완

• 배열과 달리 링크드리스트는 불연속적으로 존재하는 데이터를 연결(link)
• 데이터의 삭제: 단 한 번의 참조변경만으로 가능
• 데이터의 추가: 한 번의 Node객체생성과 두 번의 참조변경만으로 가능

이중 연결 리스트

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

  • class Node{
      Node next;
      object obj;
    }
    <!--0-->

• 더블리 써큘러 링크드 리스트 - 이중 원형 연결리스트

ArrayList(배열기반) vs LinkedList(연결기반) 비교

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