[TIL] 내일배움캠프 80일차(23.08.02.) - LinkedList 개념과 메소드, ArrayList와의 시간 복잡도 비교

To-do

• 알고리즘 문제 풀기 및 스터디
• 플러스 주차 복습 과제 작성: 게시글 삭제 API
• 스프링 심화 개선 과제 작성: Repository 테스트 코드 작성

 

---

TIL

< LinkedList 개념과 메소드>

• 참고 링크 : https://crazykim2.tistory.com/566
• LinkedList란 Collection 프레임워크의 일부이며 java.util 패키지에 소속
• 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있음
• 데이터는 포인터와 주소를 사용하여 연결, 데이터부분과 주소부분이 나눠져있어서 선으로 연결된 형태로 이어져있음

// 선언 - 타입 설정 안할 수도 있음
LinkedList<Object> list = new LinkedList<Object>();

// 값 추가
list.add(Object);
list.add(int Index, Object);
list.addFirst(Object);
list.addLast(Object);

// 값 변경
list.set(int Index, Object);

// 값 삭제
list.remove() // 첫번째 데이터 삭제
list.remove(int Index) // Index 위치의 데이터를 삭제
list.removeFist() // 첫번째 데이터 삭제
list.removeLast() // 마지막 데이터 삭제
list.clear() // 모든 데이터 삭제

// 크기 구하기
list.size()

// 값 출력
list.get(int Index)

// 값 찾기
list.contains(Object) // 값이 list에 있는지 없는지 여부 판단 -> true / false
list.indexOf(Object) // list에서 값의 Index 찾기 -> index / 없으면 -1

 

< ArrayList vs LinkedList 기본 메소드 별 시간 복잡도 비교 >

• 참고 링크 : https://sophia2730.tistory.com/entry/Data-Structure-ArrayList-vs-LinkedList

[Data Structure] ArrayList vs LinkedList

	ArrayList	LinkedList
삽입	add  >> O(1) or O(n)	add, addFirst, addLast >> O(1)
삭제	remove >> O(n)	poll, pollFirst, pollLast >> O(1)
get	get(index) >> O(1)	get(index) >> O(n)

배열에서 자주 삽입, 삭제가 이루어지는 경우 용이하여 ArrayList보다 선호되지만,
ArrayList보다 검색에 있어서는 느리다는 단점이 있다!

 

---

Next...

• JPA 강의 듣기
• 플러스 주차 복습 과제, 스프링 심화 개선 과제 작성
• 알고리즘 문제 풀기