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

리스트 삽입
- 단일 연결 리스트에 삽입하는 경우는 3가지
  
  새 노드를 가장 처음에 삽입
  
  가장 마지막에 삽입
  
  중간에 삽입
- 단일연결리스트의 가장 처음에 노드 삽입하기
  
  이 경우에는 새 노드는 현재의 head 노드 앞에 삽입됩니다.
  
  새 노드의 next 포인터를 현재의 head를 가리키도록 업데이트
  
  그리고 head 노드 포인터가 새 노드를 가리키도록 업데이트
```
def append_first(object, new_node):
    new_node.next = object.head
    object.head = new_node
```
- 가장 끝에 노드 삽입하기
  
  이 경우에는, 두 개의 next포인터를 수정해야 합니다. (마지막 노드의 'next' 포인터와 새 노드의 'next' 포인터)
  
  새 노드의 next 포인터는 NULL을 가리키고 마지막 노드의 next 포인터는 새 노드를 가리키도록
```
def append_last(object, new_node):
    current = object.head
    while current.next != None:
        current = current.next

    new_node.next = None
    current.next = new_node
```
- 중간에 노드 삽입하기
  
  새 노드를 삽입하기 원하는 위치가 주어졌다고 가정해봅시다. 이 경우에도 역시, 두개의 next 포인터를 수정해야 합니다.
  
  새 노드가 원하는 위치의 노드를 가리키게 합니다.
  
  원하는 위치의 바로 전 노드의 next 포인터가 새 노드를 가리키게 합니다.
```
def append_pos(object, new_node, pos):
    current = object.head
    if pos == 0:
        append_first(object, new_node)
        return

    for p in range(pos-1):
        current = current.next
    new_node.next = current.next
    current.next = new_node
```

시간복잡도 : O(n)

공간복잡도 : O(1)

리스트 삭제
- 단일 연결 리스트에 삭제하는 경우는 3가지
  
  가장 처음 노드 삭제
  
  가장 마지막 노드 삭제
  
  중간의 노드 삭제
- 가장 처음 노드 삭제
  
  첫 번째 노드(현재의 'head' 노드)가 리스트로부터 삭제된다.
  
  임시 노드를 만들어 'head' 노드 포인터와 같은 노드를 가리키게 한다.
  
  이제, 'head' 노드 포인터를 다음 노드로 옮기고 임시노드를 삭제한다.
```
def remove_first(object):
    first_node = object.head
    object.head = first_node.next
```
- 마지막 노드 삭제하기
  
  마지막 노드를 가리키는 포인터와 마지막 노드 하나 전 노드를 가리키는 포인터, 두 개의 포인터를 보유한다.
  
  마지막 노드 하나 전 노드의 다음 포인터를 NULL을 가리키도록 업데이트 한다.
```
def remove_last(object):
    second_last_node = object.head

    for i in range(object.ListLength()-2):
        second_last_node = second_last_node.next

    second_last_node.next = None
```
- 중간 노드 삭제하기
  
  마지막 노드를 가리키는 포인터와 마지막 노드 하나 전 노드를 가리키는 포인터, 두 개의 포인터를 보유한다.
  
  삭제할 노드를 찾았을 때 하나 전 노드의 'next' 포인터를 삭제할 노드의 'next' 포인터의 값으로 바꾼다.
  
  삭제할 현재 노드를 제거한다.
```
def remove_pos(object, pos):
    remove_node = object.head
    remove_before_node = None

    if pos == 1:
        remove_first(object)
    else:
        for i in range(pos-1):
            remove_before_node = remove_node
            remove_node = remove_before_node.next

    remove_before_node.next = remove_node.next
```
단일 연결 리스트 삭제

현재 노드의 값을 임시변수에 저장하고, 현재 노드의 메모리 할당을 해제

BEFORE

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

7강 이중 연결 리스트

BEFORE

NEXT