연결 리스트란, 각 데이터를 링크로 연결하여 관리하는 자료구조이다. 각 데이터의 하나하나를 노드(Node
)라고 부르며, 각 노드는 값과 이전 또는 다음 노드를 가리키는 주소를 가지고 있다. 맨 앞에 있는 노드를 head
노드라고 부르며, 맨 뒤에 있는 노드는 tail
노드라고 한다. 링크가 하나만 있으면 단방향 연결 리스트라고 하며, 양쪽으로 있으면 양방향 연결 리스트라고 부른다.
주요 연산으로는 삽입, 삭제, 탐색이 있으며, 모두 최악의 경우 연결 리스트의 끝까지 이동하여 연산을 실행하기 때문에 시간 복잡도는 모두 O(N)
이다.
import java.util.LinkedList;
(LinkedList
는 이전에도 예시 코드를 작성한 적 있으므로 생략. 연결 리스트를 직접 구현해보는 코드를 작성할 계획)