[멋쟁이사자처럼 유니티 TIL] 2024_12_03(화) 강의 요약 및 정리(1)

연결 리스트(Linked List)

링크드 리스트(Linked List)

 

데이터 요소들을 순차적으로 연결한 자료구조

각 노드(node)는 데이터와 다음 노드를 가리키는 포인터로 구성

메모리 상에서 연속적이지 않은 위치에 저장 가능

 

링크드 리스트의 장점

1. 동적 크기: 필요에 따라 크기 조절 가능
2. 삽입/삭제의 효율성: 포인터만 변경하면 되므로 O(1) 시간 복잡도
3. 메모리 효율: 필요한 만큼만 메모리 사용
4. 데이터 재구성 용이: 노드의 연결만 변경하여 쉽게 재구성 가능

링크드 리스트의 단점

1. 임의 접근의 비효율성: 특정 위치 접근에 O(n) 시간 복잡도
2. 추가 메모리 사용: 포인터 저장을 위한 추가 메모리 필요
3. 캐시 비효율: 메모리상 연속적이지 않아 캐시 활용도가 낮음
4. 역방향 탐색 어려움 (단일 연결 리스트의 경우)

주요 연산과 시간 복잡도

1. 접근 (Access): O(n)
2. 검색 (Search): O(n)
3. 삽입 (Insertion):
   • 맨 앞/뒤: O(1)
   • 중간: O(n)
4. 삭제 (Deletion):
   • 맨 앞: O(1)
   • 중간/뒤: O(n)

 

단일 링크드 리스트의 구조

[Data: 1, Next] -> [Data: 2, Next] -> [Data: 3, Next] -> null

- Node: 데이터를 저장하는 기본 단위

- Data: 실제 저장되는 정보

- Next: 다음 노드를 가리키는 포인터 (참조)

- null: 리스트의 끝을 나타냄

 

** 각 노드가 다음 노드만을 가리킴, 데이터의 흐름이 한 방향.

 

이중 연결(더블 링크드) 리스트 구조

null <- [Prev, Data: 1, Next] <-> [Prev, Data: 2, Next] <-> [Prev, Data: 3, Next] -> null

- Node: 데이터를 저장하는 기본 단위

- Data: 실제 저장되는 정보

- Next: 다음 노드를 가리키는 포인터 (참조)

- Prev: 현재 노드 앞에 있는 노드를 가리키는 포인터

- null: 리스트의 끝을 나타냄

 

** 각 노드가 이전 노드(Prev)와 다음 노드(Next)를 참조. 데이터의 흐름이 양방향

 

 

AddLast (맨 뒤에 추가)

- 삽입하려는 데이터를 포함하는 새 노드를 생성.

- 이 노드의 Prev와 Next를 기본값(null)으로 초기화

&리스트가 비어 있는 경우:

  리스트에 아무것도 없으면, 새 노드를 Head와 Tail로 설정

&리스트가 비어 있지 않은 경우:

  기존 Tail의 Next를 새 노드로 설정

  새 노드의 Prev를 기존 Tail로 설정

  새 노드를 Tail로 업데이트

 

AddFirst (맨 앞에 추가)

- 삽입하려는 데이터를 포함하는 새 노드를 생성

- 이 노드의 Prev와 Next를 기본값(null)으로 초기화

&리스트가 비어 있는 경우:

  리스트에 아무것도 없으면, 새 노드를 Head와 Tail로 설정

&리스트가 비어 있지 않은 경우:

  기존  Head 의 Prev 를 새 노드로 설정

  새 노드의 Next를 기존 Head로 설정

  새 노드를 Head로 업데이트