ADT(Abstract Data Type)

• abstract
  • 프로그램의 핵심부분을 간단하게 설명하기 위해 생겨남

linked-list(연결리스트)

• 리스트들을 연결해줌

  • 연결: 프로그래밍에서 참조의 기능으로 구현
    => 참조되는 노드의 '위치바꾸기'

• 리스트의 길이를 별도로 지정해줄 필요 X
  => 별도의 인덱스를 지정할 필요없이 연결되는 구조

• 연결리스트

  • 인덱스 확장
  • 요소가 참조하는 노드에 저장됨
    • 각 노드는 연결리스트의 다음 노드에 대해 참조(포인터) 함
    • 참조기호: .
    • 삽입, 할당기호: =

• 배열

  • 인덱스 접근
  • 요소를 직접 접근해 저장, 인덱스 활용

• 링크드리스트 구조

  • Node(노드): 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있음
  • Pointer(포인터): 각 노드에서 다음 데이터를 가리키는 주소값을 가짐
  • Head: 링크드리스트의 시작점인 데이터
  • Tail: 링크드리스트의 가장 마지막 데이터
  • Next=None(또는 Null): 다음 데이터가 없을 경우 포인터의 주소값은 None 또는 Null

자료구조 - 링크드리스트(Linked List)

Queue(큐)

• FIFO(선입 선출) 순서로 저장하는 자료구조

• ex) 마트 계산대 줄

  • 줄을 선 맨 첫 번째 고객이 가장 먼저 계산함

• deque

  • double-ended queue
  • 큐에서 양방향으로 데이터 처리
    • double: (자료구조에서) 양방향

• 큐의 Time and Space Complexity(시간, 공간 복잡도)

  • Enqueue(대기열에 넣기)

    • 데이터를 큐에 추가하면 (데이터를 큐 rear에 추가) O(1) 시간 걸림

  • Dequeue(대기열에서 빼기)

    • 데이터를 큐에서 빼면 (데이터를 큐 front에서 제거) O(1) 시간 걸림

• 실제로 값을 빼거나 삭제시키는 시키는 개념 X

  • enqueue

    • 새로운 노드의 저장공간(변수)를 만들어주고, 그 저장공간에 노드를 넣어주는 개념

  • dequeue

    • 삭제할 노드를 위해 저장공간(변수)를 만들어주고, 그 저장공간에 삭제노드를 넣어주는 개념

pop

• 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제

• ex)

a = [1,2,3]

a.pop() # 리스트의 맨 마지막 요소 돌려줌
# => 3

a
# => [1, 2]
# -> 돌려준 맨 마지막 요소 삭제 

리스트 요소 끄집어내기(pop)

Stack(스택)