7강 이중 연결 리스트

이중 연결 리스트 (Doubly Linked List)
- 이중 연결 리스트(혹은 양방향 연결 리스트)의 장점
  - 리스트의 특정 노드로부터 양방향으로 탐색할 수 있다.
  - 단일 연결 리스트의 노드는 바로 전 노드를 가리키는 포인터를 모르면 삭제할 수 없다.
  - 이중 연결 리스트에서는 이전 노드의 주소를 모르더라도 노드를 삭제할 수 있다. (왜냐하면 각 노드는 이전 노드를 가리키는 포인터가 있어서 리스트를 거꾸로 탐색할 수 있기 때문이다.)
- 이중 연결 리스트의 단점
  - 각 노드가 포인터를 하나식 더 필요로 하기 때문에 저장 공간이 더 필요
- 이중 연결 리스트의 노드
```
class DLLNode(object):
	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None
```
이중 연결 리스트의 삽입
- 이중 연결 리스트에 삽입하는 경우 세 가지
  - 가장 앞에 삽입하기
  - 가장 끝에 삽입하기
  - 중간에 삽입하기
- 가장 앞에 삽입하기
  
  이 경우에 새 노드는 head 노드 앞에 삽입
  
  새 노드의 next 포인터가 현재의 head 노드를 가리키도록 합니다.
  
  head 노드의 prev 포인터가 새 노드를 가리키게 합니다.
```
def append_first(object, node):
    nextn = None
    if object.head:
        nextn = object.head
        object.head = node
        object.head.next = nextn
        nextn.prev = object.head
    else:
        object.head = node
```
가장 끝에 삽입하기

이 경우에 리스트를 끝까지 탐색한 다음 새 노드를 삽입

새 노드의 next 포인터가 NULL을 가리키게 하고 prev 포인터가 리스트의 마지막 노드를 가리키게 합니다.

마지막 노드의 next 포인터가 새 노드를 가리키게 합니다.
```
def append_last(object, node):
    current = object.head
    while current.next != None:
        current = current.next

    node.next = None
    node.prev = current
    current.next = node
```
중간에 삽입하기

노드를 추가할 위치까지 리스트를 탐색한 뒤 새 노드를 삽입

새 노드의 next 포인터가 삽입하려는 위치에 있는 노드의 다음 노드를 가리키게 합니다.

새 노드의 prev 포인터가 삽입하려는 위치에 있는 노드를 가리키게 합니다.

삽입하려는 위치에 있는 노드의 다음 노드의 prev 포인터도 새 노드를 가리키게 하고, 삽입하려는 위치에 있는 노드의 next 포인터가 새 노드를 가리키게 합니다.
```
def append_pos(object, node, pos):
    current = object.head
    if pos == 0:
        append_first(object, node)
        return

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

    prevn = current.prev
    node.next = current
    prevn.next = node
    node.prev = prevn
    current.prev = node
```

시간 복잡도 : O(n)

공간 복잡도 : O(1)

이중 연결 리스트의 노드 삭제
- 이중 연결 리스트의 노드를 삭제하는 경우 세 가지
  - 가장 앞 노드 삭제하기
  - 가장 끝 노드 삭제하기
  - 중간에 있는 노드 삭제하기
- 가장 앞 노드 삭제하기
  
  이 경우에 첫 번째 노드가 리스트로부터 삭제
  
  임시 노드를 만들어 head 노드 포인터와 같은 노드를 가리키게 합니다.
  
  head 노드 포인터를 다음 노드로 옮기고 head 노드의 prev 포인터를 NULL을 가리키게 합니다. 그런 다음 임시 노드를 삭제합니다.
```
def remove_first(object):
    first_node = object.head
    object.head = first_node.next
    object.head.prev = None
```
가장 끝 노드 삭제

리스트의 끝까지 탐색합니다.

마지막 노드 하나 전 노드의 next 포인터를 NULL을 가리키게 합니다.

마지막 노드를 제거합니다.
```
def remove_last(object):
    current = object.head
    while current.next != None:
        current = current.next

    current.prev.next = None
```
중간에 있는 노드 삭제

삭제할 노드를 찾을 때까지 리스트를 탐색

삭제할 노드를 찾으면 삭제할 노드 하나 전 노드의 next 포인터를 삭제할 노드 다음 노드를 가리키도록 합니다.

삭제할 노드 다음 노드의 prev 포인터를 삭제할 노드 하나 전 노드를 가리키도록 합니다.

현재 삭제할 노드를 제거합니다.
```
def remove_pos(object, pos):
    current = object.head

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

        prevn = current.prev
        nextn = current.next
        prevn.next = current.next
```

BEFORE

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

8강 스택, 스택의 구현

BEFORE

NEXT