[Java | 자료구조] 연결 리스트 (Linked List)

연결 리스트(Linked List)

• 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시켜 저장하는 방식의 선형 자료구조

특징

• K번째 원소를 확인/변경하기 위해 O(k)가 필요
• 임의의 위치에 원소를 추가/제거는 O(1)

종류

1. 단일 연결 리스트(Singly Linked List)
   • 각 원소가 자신의 다음 원소의 주소를 포함하고 있음
   • 이전 원소가 무엇인지 알 수 없음
   • 마지막 노드의 링크값은 null
2. 원형 연결 리스트(Circle Linked List)
   • 끝이 처음과 연결되어 있음
   • 마지막 노드의 링크가 첫 번째 노드를 가리킴
   • 각 원소가 자신의 이전 원소와 다음 원소의 주소 둘 다 포함하고 있어도 상관없음
3. 이중 연결 리스트(Doubly Linked List)
   • 각 원소가 자신의 이전 원소와 다음 원소의 주소 둘 다 포함하고 있음
   • 이전 원소가 무엇인지 알 수 있음
   • 메모리를 더 많이 사용

시간복잡도

	배열	연결 리스트
k 번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간	-	O(N)

구현

LinkedList<Integer> list = new LinkedList<>();

// 생성시 초기값 설정 불가
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));

list.addFirst(1)   // 맨 앞에 1 추가
list.addLast(5)   // 맨 뒤에 5 추가
list.add(6)  	 // 마지막에 6 추가 성공하면 ture 반환
list.add(2, 3)  // index 2에 3 추가

list.removeFirst() // 첫 번째 노드 제거
list.removeLast()  // 마지막 노드 제거
list.remove(2)  // index 2 위치 요소 제거
list.clear() // 완전히 비우기

list.size()  // 저장된 객체의 개수 반환
list.isEmpty()  // 비어있으면 true
list.contains(3)  // 3이 포함되어있으면 true
list.indexOf(1)  // 1이 저장된 위치 반환
list.lastIndexOf(1)  // 1이 저장된 위치를 뒤에서부터 역방향으로 찾아 반환

list.get(1)  // index 1에 저장된 객체 반환
list.subList(3, 5)  // 3부터 5 사이에 저장된 객체 리스트로 반환

list.set(3, 6)  // index 3의 객체를 6으로 변경

list.toArray()  // 저장된 모든 객체들 객체배열로 반환

• 이 외에 스택, 큐의 메소드도 사용 가능