5강 단일 연결 리스트, 연결 리스트의 장단점

연결리스트의 장점
- 상수 시간안에 확장 가능
- 배열을 만들기 위해서는 특정한 갯수의 항목을 할당해야만 합니다.
  
  배열에 항목을 추가하기 위해서는 새 배열을 만들어 원래 배열에서 새 배열로 항목들을 복사해야합니다.
  
  이 방법은 시간이 오래걸립니다.
  
  이를 막기 위해 처음에 많은 공간을 할당할 수도 있지만 메모리가 낭비될 수 있습니다.
- 연결리스트를 사용하면 하나의 항목을 위한 공간으로 시작해서 복사나 재할당 없이 새 항목을 쉽게 추가할 수 있습니다.
연결리스트의 단점
- 개별 항목에 접근하는 접근 시간이 오래 걸립니다.
- 배열은 랜덤 접근이 가능하므로 배열의 항목에 접근하는데 O(1)의 시간이 걸립니다.
- 연결리스트는 리스트의 항목에 접근하는데 최악의 경우 O(n)의 시간이 걸립니다.
- 접근 시간에 있어서 배열의 또 다른 장점은 메모리 안에서의 특수한 locality(지역성)입니다.
  
  배열은 연속된 메모리 블록으로 정의되므로 배열의 항목들은 물리적으로 근처에 위치
- 비록 저장 공간의 동적 할당이 큰 장점이긴 하지만 데이터의 저장과 인출에 더해지는 부담이 큰 차이를 만듭니다.
  
  때로 연결 리스트는 변경하기가 어렵습니다.
  
  마지막 항목이 삭제되면, 가장 끝에서 하나 전의 항목의 포인터가 NULL을 가리키도록 변경되어야만 합니다.
  
  끝에서 하나 전의 항목을 찾아 그 포인터가 NULL을 가리키게 하기 위해 리스트가 탐색되어야 합니다.
- 추가적인 참조 포인트를 위한 메모리 공간이 낭비
단일 연결리스트

일반적으로 linked list는 singly linked list를 의미합니다.

이 리스트는 다음 노드를 가리키는 next 포인터를 가진 노드들의 집합으로 이루어집니다.

마지막 노드는 NULL을 가리켜 리스트의 마지막임을 나타냅니다.

정수를 저장하는 연결 리스트의 노드는 다음과 같이 선언됩니다.
```
class Node(object):
	def __init__(self, data):
		self.data = data
		self.next = None
```
리스트의 기본 연산

리스트 탐색

리스트에서 항목 삽입

리스트에서 항목 제거
리스트 탐색
- head 노드 포인터가 리스트의 첫 번째 노드를 가리킨다고 가정
  
  포인터를 따라간다
  
  탐색하면서 노드의 값을 표시한다. (또는 갯수를 계산)
  
  next 포인터가 NULL을 가리키면 멈춘다.
- ListLength()는 연결 리스트를 받아 리스트의 노드 갯수 계산
```
def ListLength(object):
    count = 0
    current = object.head
 
    while current.next != None:
        count += 1
        current = current.next
    count +=1

    return count
```
  시간 복잡도 : 크기가 n인 전체 리스트를 스캔하는데 O(n)
  
  공간 복잡도 : 하나의 임시 변수를 만드는 데 O(1)

BEFORE

4강 재귀와 반복 비교, 연결 리스트

6강 단일 연결 리스트의 삽입

BEFORE

NEXT