연결 리스트(Linked List)

AmeriKano·2023년 3월 17일
0

자료구조

목록 보기
5/5

<연결 리스트 노트 정리>

연결 리스트란?

연결 리스트란, 각 데이터를 링크로 연결하여 관리하는 자료구조이다. 각 데이터의 하나하나를 노드(Node)라고 부르며, 각 노드는 값과 이전 또는 다음 노드를 가리키는 주소를 가지고 있다. 맨 앞에 있는 노드를 head 노드라고 부르며, 맨 뒤에 있는 노드는 tail 노드라고 한다. 링크가 하나만 있으면 단방향 연결 리스트라고 하며, 양쪽으로 있으면 양방향 연결 리스트라고 부른다.

주요 연산과 시간 복잡도

주요 연산으로는 삽입, 삭제, 탐색이 있으며, 모두 최악의 경우 연결 리스트의 끝까지 이동하여 연산을 실행하기 때문에 시간 복잡도는 모두 O(N) 이다.

연결 리스트의 장점

  • 따로 길이를 지정하지 않으므로 길이가 가변적이다.
  • 데이터의 삽입과 삭제가 배열보다 훨씬 편리하다.

연결 리스트의 단점

  • 배열과는 달리 인덱스를 활용할 수 없으므로 데이터 탐색에 시간이 소요된다. (찾을 때까지 리스트의 데이터를 확인해야 하기 때문)
  • 값을 저장하는 데이터 공간뿐만 아니라 링크 정보를 위한 공간도 필요하다.
  • 데이터 삽입/삭제 시 링크를 재구성(다른 곳에 연결하거나 끊는 등)하는 과정이 필요하다.

JAVA에서의 연결 리스트 사용

import java.util.LinkedList;

(LinkedList는 이전에도 예시 코드를 작성한 적 있으므로 생략. 연결 리스트를 직접 구현해보는 코드를 작성할 계획)

profile
똑똑한 사람이 되게 해주세요

0개의 댓글