[자료구조] 연결 리스트

연결리스트 정의

- 연결리스트는 데이터와 포인터를 가지고 있는 노드를 한 줄로 연결하여 데이터를 저장하는 자료구조

- 포인터는 다음이나 이전의 노드와 연결을 담당

- 연속된 메모리 구조가 아닌 파편화된 메모리에서 유용하게 사용

- 접근 시간 복잡도: O(N)

- 탐색 시간 복잡도: O(N)

- 삽입/삭제 시간 복잡도: O(1)

연결리스트 종류

- Single Linked List: 각 노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노드를 가리킴

- Doubly Linked List: 노드에 앞 노드의 메모리 주소를 보관하는 포인터를 추가해 앞의 노드와 뒤의 노드 모두 연결

- Circular Linked List: Single Linked List의 마지막 노드의 포인터가 NULL이 아닌 헤드를 가리키는 형태

- Doubly Circular Linked List: Doubly Linked List 맨 앞의 노드의 포인터와 맨 끝의 노드의 포인터가 NULL이 아닌 서로를 가리키는 형태

 

연결리스트 ADT

 

연결리스트 구현

프로그램 언어별 메서드

- C

 

- C++

 

- C#

 

- Java

 

- Python: 파이썬의 리스트는 연결리스트로 구현되어 있음

// 연결리스트 생성
ll = list()
ll = []

// 연결리스트 초기화
ll = [None for _ in range(size)]
ll = [val1, ...]

// 값 접근
ll[index]

// 값 수정
ll[index] = val

// 값 추가
ll.append(val)
ll.insert(val, idx)

// 값 삭제
ll.remove(val)
ll.pop(index)
del ll[index]

- JavaScript