[자료구조] LinkedList

LinkedList 는 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지 않는 자료구조로 단방향, 양방향, 원형으로 구현할 수 있다. 데이터를 동적 할당할 수 있고, 데이터 추가/삭제가 용이하다는 장점이 있지만, 데이터를 검색할 때에는 Array에 비해 상대적으로 느리다는 단점이 있다. Java 내에서는 Garbage Collection(가비지 컬렉션 : 불필요한 메모리를 알아서 정리) 기능이 있어 삭제 시에 다음 Pointer를 Null로 변경해주면 LinkedList 상에서 데이터 삭제된 걸로 구현할 수 있으며, 가르키는 포인터가 삭제된 데이터는 메모리 상에서 삭제된다.

 

단방향 LinkedList

LinkedList 의 시간 복잡도

 

접근, 검색 : O(n)

추가/삭제 : O(1)

 

java LinkedList ( java.util.LiskedList)

 

1) 데이터 추가

• 맨 앞
  1. addFirst(Object)
  2. offerFirst(Object)
• 맨 뒤
  1. add(Object)
  2. addLast(Object)
  3. OfferFirst(Object)
  4. OfferLast(Object)
• 위치지정
  1. add(int index, Object) : index 위치에 데이터(Object)를 추가, index 입력 생략 시 맨 뒤에 추가됨
  2. addAll(int index, Collection) : index 위치에 컬렉션 데이터를 추가, index 입력 생략 시 맨 뒤에 추가됨
• 객체 포함 유무를 확인하는 메서드
  1. contains(Object) : 매개변수로 넘긴 데이터가 있을 경우 true를 리턴
  2. indexOf(Object) : 매개변수로 넘긴 데이터의 맨 앞 위치를 리턴하고, 없을 경우 -1 리턴
  3. lastIndexOf(Object) : 매개변수로 넘긴 데이터의 맨 뒤 위치를 리턴하고, 없을 경우 -1 리턴

 

2) 데이터 삭제

• 맨 앞
  1. remove()
  2. removeFirst()
• 맨 뒤
  1. removeLast()
• 지정삭제
  1. remove(int index) : index 위치의 데이터를 삭제
  2. remove(Object) : 매개변수로 넘어온 객체와 동일한 데이터를 삭제

 

 

 

출처 :

https://mangkyu.tistory.com/118 : Garbage Collection 설명

https://chunsubyeong.tistory.com/15 : java.util.LinkedList method