# 연결 리스트 (Linked List)
# 연결 리스트란 무엇인가요?
- 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조입니다.
- Node로 연결한 구조이며, 각 Node들은 데이터와 다음 Node에 대한 참조(주소)값을 가지고 있습니다.
- Collection 프레임워크의 일부이며 java.util 패키지에 LinkedList로 소속되어 있습니다.
# 연결 리스트 종류
- 싱글 연결 리스트 : next 포인터만 가집니다.
- 이중 연결 리스트 : next 포인터와 prev 포인터를 가집니다.
- 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킵니다.
참고로, java util패키지의 LinkedList는 이중 연결 리스트와 같은 형식으로 구성되어있습니다.
# 연결 리스트 사용법
- LinkedList 선언
LinkedList list = new LinkedList(); //타입 미설정
LinkedList<Integer> num = new LinkedList<>(); //int타입만 집어넣을 수 있음
- LinkedList 값 추가
list.add(3); // 3이라는 데이터 추가 (맨 뒤에 추가됨)
list.add(2, 5); // index 2에 데이터 5 추가
list.addFirst(1); // 맨 앞 노드에 데이터 추가
list.addLast(2); // 맨 뒤 노드에 데이터 추가
- LinkedList 값 삭제
list.remove(); // 맨 뒤에 있는 노드 제거
list.remove(1); // index 1 제거
list.removeFirst(); // 맨 앞 노드 삭제
list.removeLast(); // 맨 뒤 노드 삭제
list.clear(); //모든 노드 삭제
- LinkedList 데이터 변경
list.set(2, 10); // 2번 index에 있는 값을 10으로 변경
- LinkedList 크기 구하기
list.size(); // 리스트의 크기 구하기
- LinkedList 값 검색
list.contains(1); // 리스트에 1이 존재하면 true 반환, 없으면 false
list.indexOf(1); // 1이 있는 index 반환, 없으면 -1
- LinkedList 값 출력하기
list.get(i); // i번 index에 있는 데이터 출력
list.getFirst(); // 맨 앞에 있는 데이터 출력
list.getLast(); // 맨 뒤에 있는 데이터 출력
for(Integer i : list) { // 향상된 for문을 통한 전체출력
System.out.println(i);
}
Iterator<Integer> iter = list.iterator(); // Iterator 선언
while(iter.hasNext()){//다음값이 있는지 체크
System.out.println(iter.next()); //값 출력
}
# 연결 리스트의 시간 복잡도는 얼마나 되나요?
삽입과 삭제에는 O(1), 탐색에는 O(n)이 걸립니다.
# 연결 리스트를 사용하는 이유는 무엇인가요?
- 리스트의 길이가 가변적이기 때문에 메모리 효율성이 좋습니다.(새로운 요소가 추가될 때, 런타임에 메모리를 할당한다.(동적메모리 할당))
- 데이터의 추가, 삭제가 편리합니다.
따라서 새로운 데이터를 추가하거나 삭제해야하는 작업이 빈번히 일어날 때 사용하기 좋습니다.
# 연결 리스트의 단점은 무엇이 있나요?
어떤 노드를 search 하거나 데이터를 변경할 때 바로 찾아낼 수 없습니다.
최악의 경우에는 모든 노드를 방문하고 맨 마지막에 있는 노드를 얻는 행위를 반복할 수도 있습니다. (시간 복잡도 : O(n))
# 참고자료
출처: 주홍철.면접을 위한 CS 전공지식 노트.서울:길벗,2022.
출처: https://coding-factory.tistory.com/552