<aside> 😊 linkedlist의 개념과 특징 배열의 단점을 정리한 페이지입니다 :)

</aside>

LinkedList

• LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어서 참조하려는 원소에 따라 처음부터 순방향으로 또는 역순으로 순화할 수 있음 (배열의 단점을 보완하기 위해서 LinkedList라는 자료구조가 고안됨)

배열의 단점

• 크기를 변경할 수 없음
  • 크기를 변경할 수 없으므로 새로운 배열을 생성해서 복사해야 함
  • 실행속도를 향상시키기 위해서는 충분히 큰 용량을 미리 정해놔야 하는데 이것이 메모리 낭비가 될 수 있음
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸림
  • 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠름
  • 배열의 중간에 데이터를 추가하거나, 삭제하면 빈공간을 만들기 위해 데이터 이동이 필요하고, 빈 공간을 채우기 위해 데이터 이동이 빈번

LinkedList API의 특징

• add(E element) : 원소를 마지막에 추가하기
  • LinkedList도 마찬가지로 add 메소드가 존재
  • LinkedList는 배열처럼 인덱스를 가지고 있지 않음
  • 원소를 추가하기 위해서는 헤더에서부터 마지막까지 찾아가야 하기 때문에 시간이 많이 걸림
• add(int index, E element) : 원소를 지정된 위치에 추가하기
  • 인덱스를 지정해서 추가하는 것도 마찬가지로 해당 위치로 가려면 헤더부터 탐색해서 가야하기 때문에 시간이 걸리게 됨
• remove(int index) : 원소를 삭제하기
  • 원소를 삭제하려면 배열의 경우는 삭제하면 빈 공간을 다시 채워주는 작업이 필요하지만, LinkedList는 삭제하려는 원소 앞 or 뒤로 가서 가르키는 값을 null로 바꿔주면 됨
• get(int index) : 인덱스에 해당하는 원소 찾아오기
  • LinkedList는 ArrayList와 다르게 인덱스를 통해서 검색을 하는 것이 아니라 Head에서 부터 해당원소까지 검색해야 하기 때문에 O(n)에 찾을 수 있음