자료구조란?

• 자료구조의 가장 기본적인 의미
  • 자료를 쉽게 관리하기 위해 다양한 구조로 묶는 것이다
  • 자료구조 : 자료를 저장하는 방법
    • data structure -> 자료구조, 자료 -> 데이터
  • 다양한 자료구조 -> 각각의 자료구조마다 장단점이 존재

자료구조 사용하면 좋은점?

• 똑같은 알고리즘도 어떤 데이터 구조를 사용하는지에 따라 효율성이 달라진다.
  • 모든 자료구조가 같은 효율성을 지니고 있지 않다.
  • 배열은 배열 안에 있는 자료를 불러오는 것이(Read) 빠르다.
  • 연결리스트
    • 연결리스트 같은 경우 n번째 자료에 접근하기 위해서 1번부터 모든 데이터를 거쳐서 가야하니 때문에, Read연산이 느리다.(단점)
    • (장점) 연결리스트는 새로운 데이터를 삭제, 새로운 데이터를 추가하는 연산이 빠르다! 반면에 배열의 경우는 경우에 따라 느리다.
    • 확장/축소(크기)
• 데이터를 관리하는데 도움이 된다.
  • 선착순 -> 수강신청, 티켓팅
  • 배열, 큐 자료구조

배열에 대해서

• 기본적인 자료구조 배열
• 선형자료구조 -> 자료를 순차적으로 나열
  • 배열
    • 정해진 크기의 같은 타입의 데이터를 저장하는 구조
  • 동적배열
    • 크기가 정해지지 않은 데이터를 저장하기 위해고안됨
  • 연결리스트
    • 각각의 데이터가 다음 데이터를 가르키도록 해서 중간에 추가나 제거가 쉽게 되도록 고안됨
• 비선형 자료구조 -> 하나의 저료 뒤에 다수의 자료가 올 수있는 형태

연결리스트, 자료구조의 시간복잡도

• 자료구조의 시간복잡도
  • 데이터 연산 4개 : Read, Search, Add, Delete
• 연결리스트
  • 종류
    • 노드당 다음 노드를 알려주는 링크가 하나밖에 없다면 : 싱글리 링크드 리스트
      • 한방향으로 밖에 이동을 못한다.
    • 노드당 링크 2개, 이전 노드를 갈 수 있는 링크가 추가하게 된다면 더블리 링크드 리스트
      • 양방향으로 움질일 수 있다.
    • 환형 리크드 리스트 (Circular)
      • 더블일 수도 있고, 싱글일 수도 있는데
        • 계속 앞으로 앞으로 가서 맨 마지막 노드에 도착했을떄 다임이 어디야! 했을때 처음으로 알려주는 순환이 되는 형태를 환형 링크드 리스트라고 합니다.
        • 마지막 노드가 첫번쨰 노드를 가르켜서 계속 회전할 수 있게 만드는 연결리스트

추상화에 대한 설명

• 추상화
  • 핵심 개념이나 기능을 간추려 내는 것 -> 개념을 만들어가는 과정

ADT

• 추상 자료형
  • 세부 구현으로부터 분리해 핵심 개념이나 기능을 간추려 낸 자료형
• 스텍, 큐, 리스트, 이진트리 같은 자료구조도 추상자료형
• 프로그래밍 관점에서 추상 자료형의 장점은
• 반드시 필요한 기능이지만 내부 구현을 사용자에게 맡김으로서 사용의 유연함을 제공할 수 있다.(다형성)
• 스택, 큐
  • 규칙을 이해

스택, 큐

• 스택
  • 후입선출
• 큐
  • 선입선출
  • 줄서기

---

동적배열과 연결리스트

• 두 자료구조의 차이점은 삽입과 삭제, 그리고 임의의 원소에 접근하는데 드는 시간입니다.

스택과 큐 정의와 용어
LIFO : 스택
FIFO : 큐

스택

• 자료의 입출력이 한 방향에서만 이루어지는 자료구조
• 스택의 주요기능
  • push : 스택에 데이터를 추가하는 기능
  • pop : 스택에 최상의 데이터를 꺼내는 기능
  • 스택의 맨 위 값을 가리키는 용어 : top, peek, head

큐

• 한 쪽 끝에서 삽입만 가능하고, 반대쪽 끝에서만 삭제만 가능한 자료구조
• 데이터를 꺼내는 쪽을 front, 데이터를 넣는 쪽을 rear
• 큐에서 front는 맨 앞의 원소를 가리키고, rear는 맨 끝의 원소를 가리킵니다.
  • enqueue : 큐에 값을 집어넣는 함수(스택의 push역할)
  • dequeue : 큐에 값을 빼내는 함수(스택의 pop역할)