Linked List

연결리스트

• 데이터를 링크로 연결해서 관리하는 자료구조
• 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않는다.

연결리스트의 장점

• 데이터 공간을 미리 할당할 필요가 없다.
• 리스트의 길이가 가변적이라 데이터 추가 / 삭제가 용이하다.

연결리스트의 단점

• 연결구조를위한 별도 데이터 공간 필요
• 연결정보를 찾는 시간필요 (접근 속도가 상대적으로 느림
• 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업이 필요

연결리스트 기본 구조

노드 : 데이터 저장 단위로, 값과 포인터로 구성된다.

연결리스트의 기본 연산

추가

가장 앞에 추가

1. 추가할 데이터 담을 노드 생성
2. 새 노드의 next를 head노드로 연결
3. head 새로 지정

중간에 추가

1. 추가할 데이터를 담을 노드 생성
2. head부터 추가 위치 직전까지 순회
3. 링크 연결

끝에 추가

1. 추가할 노드 생성
2. head부터 끝까지 순회
3. 링크연결

삭제

가장 앞 노드 삭제

1. 삭제할 노드 지정
2. head를 다음 노드로 옮김
3. 노드 삭제

중간 노드 삭제

1. head에서 삭제 대상 노드까지 이동 및 삭제 노드 지정
2. 삭제 노드의 이전노드와 다음 노드 링크 연결
3. 삭제 노드 삭제

마지막 노드 삭제

1. head에서 끝까지 순회
2. 끝 노드 삭제

연결리스트 선언

선언

import java.util.LinkedList;
LinkedList<Integer> list = new LinkedList<>();

메소드

list.add(val) : 맨 뒤에 val추가
list.add(idx, val) : idx위치에 val추가
list.addFirst(val) : 처음에 val추가
list.addLast(val) : 마지막에 val추가
list.set(idx, val) : 특정 위치에 노드 추가

list.removeLast(): 마지막 노드삭제
list.removeFirst() : 첫번째 노드 삭제

list.get(idx) : idx위치 값 반환
list.contains(val) : val의 포함 여부 반환
list.size() : list의 크기 반환

head 추출
list.getFirst()
list.peek()
list.peekFirst()

tail추출
list.getLast()
list.peekLast()

head 추출 후 삭제
list.poll()
list.pollFirst()

tail 추출 후 삭제
list.pollLast()

연결 리스트 시간 복잡도

동작	시간복잡도
접근	$O(n)$
추가 / 제거	$O(1)$

링크드 리스트는 삽입 / 삭제가 자주 일어나는 동적 데이터를 관리하기에 용이하다!