연결 리스트 (Linked List)

연결 리스트

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다.
각 요소는 노드라고 부르고 데이터 영역과 포인터 영역으로 나뉜다

연결 리스트 특징

• 메모리가 허용되는 범위에서 제한없이 요소 추가가 가능하다.
• 요소 탐색은 O(n)이 소요된다.
• 요소 추가, 제거는 O(1)이 소요된다.
• Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다.

배열과의 차이점

메모리 차이

• 배열은 순차적 데이터를 다루므로 메모리의 영역을 연속적으로 사용한다.
  하지만 연결 리스트는 각 데이터가 퍼져있기 때문에 메모리 영역이 넓다.
  => 각 영역을 찾기 위해 포인터를 참조한다.

• 배열은 요소 추가 삭제가 O(n)이나 연결 리스트는 O(1)이 소요된다.
  => 연결 리스트는 추가, 삭제하기 위해 포인터만 바꿔주면 되므로 시간복잡도가 낮다.

Singly Linked List (단일 연결 리스트)

Head에서 Tail까지 단방향으로 이어지는 연결 리스트이다.
가장 단순한 형태의 연결 리스트이다.
끝 요소의 포인터는 NULL로 지정되어 있다.

단일 연결 리스트 요소 찾기, 추가, 삭제

• 찾기
  포인터가 가르키는 데이터를 확인하면서 찾는다. O(n)

• 추가

  1. 삽입 데이터 포인터 영역을 삽입 위치 데이터 영역에 연결한다.
  2. 삽입 데이터 데이터 영역을 삽입 위치 이전의 포인터 영역과 연결한다.
  3. 기존 포인터, 데이터 영역 연결을 삭제한다. O(1) 소요

• 삭제

  1. 삭제할 요소 이전 요소의 포인터 영역이 삭제할 요소 이후 요소의 데이터 영역에 연결한다.
  2. 삭제할 요소를 삭제한다. O(1) 소요

단일 연결 리스트 코드 실습

과제

• SinglyLinkedList 클래스에 리스트 크기를 구하는 'size' 메소드 만들기
• 만든 SinglyLinkedList의 예외 처리 추가하기

Doubly Linked List (이중 연결 리스트)

양방향으로 이어지는 연결 리스트이다.
Singly Linked List보다 자료구조의 크기가 조금 더 크다.

이중 연결 리스트 요소 찾기, 추가, 삭제

• 추가 : O(1) 소요
  1. 추가할 요소의 다음 노드 포인터가 다음 요소를 가르키도록 한다.
  2. 추가할 요소의 이전 요소의 다음 노드 포인터가 추가할 요소 데이터 영역을 가르키도록 한다.
  3. 추가할 요소의 다음 요소의 이전 노드 포인터가 추가할 요소를 가르키도록 한다.
  4. 추가할 요소의 이전 노드 포인터가 이전 요소를 가르키도록 한다.
• 삭제 : O(1) 소요
  1. 삭제할 요소 이전 요소의 다음 노드 포인터가 삭제할 요소 다음 요소를 가르키게 한다.
  2. 다음 요소 이전 노드 포인터가 이전 요소를 가르키도록 한다
  3. 삭제할 요소를 삭제한다.

과제

SinglyLinkedList 클래스를 참고하여 DoublyLinkedList를 구현

Circular Linked List (환형 연결 리스트)

Singly 또는 Doubly Linked List에서 Tail이 Head로 연결되는 리스트이다.
메모리를 아낄 수 있고 원형 큐 등을 만들 때 사용된다.

과제

SinglyLinkedList 클래스를 참고하여 CircularLinkedList를 구현
힌트 : 탐색 종료 조건이 있어야 한다.