[인프런 김영한 실전 자바 - 중급편] 컬렉션 프레임워크 - LinkedList

연결 리스트(링크드 리스트) - LinkedList

• Node : 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.

• LinkedList : 각각의 노드를 연결(링크)해서 사용하는 List 자료 구조다.
  
  • List의 특징인 데이터에 순서가 있고 중복을 허용한다.
  • 각각의 노드가 참조를 통해 연결(링크)되어 있다.
  • 데이터를 추가할 때 동적으로 필요한만큼의 노드를 만들어서 연결할 수 있다.
    • 배열과 다르게 메모리를 낭비하지 않는다.

 

• LinkedList vs ArrayList
  • ArrayList는 리스트 내부에서 배열을 사용한다.
    
    • 내부에서 배열을 사용하기에 인덱스로 조회하는데는 O(1)로 빠르게 찾을 수 있다.
    • 값을 추가, 삭제하는 등의 변경은 값을 앞 / 뒤로 밀어야하기 때문에 O(n)이 소요된다.
    • 데이터를 찾는 것은 빠르지만 데이터를 넣고 빼는 것이 느리다.
  • LinkedList는 리스트 내부에서 노드를 사용한다.
    • 내부에서 노드를 사용하기에 인덱스로 조회하는데 반복해서 다음 노드를 찾아가야 하므로 O(n)이 소요된다.
    • 값을 추가, 삭제하는 등의 변경은 값을 앞 / 뒤로 밀 필요 없이 노드의 참조만 바꾸면 되기에 O(1)로 빠르게 처리한다.
    • 데이터를 넣고 빼는 것은 빠르지만 데이터를 찾는 것이 느리다.

 

• LinkedList의 Big O
  
  • 인덱스 조회 O(n) - 연결리스트에서는 배열을 사용하지 않기에 인덱스 위치의 값을 찾기 위해서는 그만큼의 다음 노드를 반복해서 찾아야 한다.
    연결리스트의 인덱스 조회 성능은 나쁘다.
  • 데이터 추가, 삭제 O(n) - 첫 번째에 추가하는 경우 배열처럼 앞 / 뒤로 밀지 않고 노드의 참조만 변경해서 O(1)이 소요된다.
    하지만 중간이나 마지막에 추가하는 경우 마지막 노드를 찾는데 O(n)이 소요되므로 총 O(n)만큼 소요된다.
  • 데이터 검색 O(n) - 모든 노드를 순회하면서 데이터를 검색하기에 O(n)이 소요된다.

	ArrayList	LinkedList
인덱스 조회	O(1)	O(n)
검색	O(n)	O(n)
앞에 추가 / 삭제	O(n)	O(1)
뒤에 추가 / 삭제	O(1)	O(n)
평균 추가 / 삭제	O(n)	O(n)

• 데이터를 조회하고 뒤에 추가 / 삭제할 일이 많은 경우 ArrayList가 더 좋은 성능을 제공한다.
  데이터를 앞에 추가 / 삭제할 일이 많은 경우 LinkedList가 더 좋은 성능을 제공한다.

 

• 단일 연결 리스트
  
  • 한 방향으로만 이동하는 연결 리스트다.
• 이중 연결 리스트
  • 노드를 앞뒤로 모두 연결하여 양방향으로 이동하는 연결 리스트다.
  • 자바가 제공하는 연결 리스트는 이중 연결 리스트다.
  • 양방향으로 이동할 수 있기 때문에 뒤에서 데이터를 추가 / 삭제하는 경우에도 O(1)로 빠른 성능을 제공한다.

 

• 자바의 LinkedList의 특징
  
  • 이중 연결 리스트 구조
    • 다음 노드, 이전 노드로 이동할 수 있다.
  • 첫 번째 노드와 마지막 노드 둘 다 참조
    • 마지막 노드에 대한 참조도 가지기 때문에 데이터를 마지막에 추가하는 경우에도 빠른 성능을 제공한다.
    • 인덱스를 조회하는 경우에도 마지막 노드부터 조회함으로 성능을 최적화 할 수 있다.

---

출처: [인프런 김영한 실전 자바 - 중급편]

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2/dashboard

김영한의 실전 자바 - 중급 2편 강의 | 김영한 - 인프런