Singly Linked List

모든 node stores는
1. element
2. link to the next node
로 구성

• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조임.

참조 https://velog.io/@hyhy9501/5-1-Linked-List-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4

linked list의 핵심요소

• Node(노드)
  : 링크드 리스트의 기본 단위.
  : 데이터를 저장하는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성
• Pointer(포인터)
  : 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 ㄴ공간
• Head(헤드)
  : 링크드 리스트에서 가장 처음 위치하는 노드를 가리킴.
  : 리스트 전체를 참조하는데 사용
• Tail(테일)
  : 링크드 리스트에서 가장 마지막에 위치하는 노드를 가리킴
  : 이 노드의 링크 필드는 Null을 가리킴

The Node Class for List Nodes(java)

Inserting at the Head

1. Allocate a new node
   : 새로운 노드를 할당하고
2. Insert new element
   : 새로운 노드 안에 값을 넣음
3. Have new node point to old head
   : 그 후 새로운 노드의 포인트를 예전의 head를 가리키게 함
4. Update head to point to new node
   : head를 새로운 노드를 가리키게 함.

Removing at the Head

1. Update head to point to next node in the list
   : head를 다음 노드를 가리키게 함.
2. Allow garbage collector to reclaim the former first node
   : garbage collector가 former first node를 없애게 해줌.

Inserting at the Tail

1. Allocate a new node
   : 새로운 노드를 할당
2. Insert new element
   : 새로운 노드에 요소 삽입
3. Have new node point to null
   : 새로운 노드가 null을 가리키게 함
4. Have old last node point to new node
   : 예전 null을 가리키던 노드를 새로운 노드를 가리키게 함
5. Update tail to point to new node
   : tail이 새로운 노드를 가리키게 함

Removing at the Tail

1. Removing at the tail of a singly linked list is not efficient!
   : 단일 연결 리스트의 tail을 제거하는 건 비효율적임.
2. There is no constant-time way to update the tail to point to the previous node
   : 상수 시간 내에 작업을 완료할 수 없음.

단일 연결 리스트의 성능

1. 제일 앞(뒤) 삽입 → O(1)
2. 제일 앞 삭제 → O(1)
3. 제일 뒤 삭제 → O(n)
4. 탐색/접근 → O(n)

배열에서는 노드 추가 O(n), 접근 O(1)

Stack as a Linked List

• 공간 사용: O(n)
• 시간 사용: O(1)
  

Queue as a Linked List

• 공간 사용: O(n)
• 시간 사용: O(1)
  

Double Linked Lists

• Nodes implement Position and store

1. element
2. link to the previous node
3. link to the next node

Insertion

1. X node의 next를 C를 가리키게 함
2. X node의 prev를 B가 가리키게 함
3. C node의 현재 prev를 끊고, X node를 가리키게 함.
4. B node의 현재 next를 끊고, X node를 가리키게 함.

Deletion

1. C node의 next가 trailer를 가리키게 함
2. trailer가 C node 를 가리키게 함
3. D node의 prev와 next를 끊음
4. D node를 삭제함.

Doubly Linked List in Python

Performance

• In Double Linked List...

1. 공간 사용: O(n)
2. 각각의 노드가 차지하는 공간 O(1)
3. 시간 사용: O(1)

참고 https://velog.io/@harper9808/deque%EB%8A%94-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80

Deque(Double Ended Queue, 데크)

• 디큐가 아님!
• 데크는 양방향 큐
• 즉, 앞 뒤 방향에서 element를 추가/삭제 가능
• 결국 양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상 자료형
• 파이썬은 데크 자료형을 Collections 모듈에서 deque라는 이름으로 지원
• 이중 연결 리스트로 구현
• 데크는 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑

Deque in Python