자료구조1

자료구조 1

배열, 문자열

배열

특징

• 데이터들이 순차적으로 나열되어 있는 자료구조
• 요소들의 집합, 특정 인덱스를 통해 요소에 접근할 수 있음
• 하나의 연관된 데이터를 그룹으로 다루기 위해 사용
• 여러 형태로 사용 가능(1차원, 2차원, 3차원 등)
• 여러 자료 구조에서 직간접적으로 사용됨
• 탐색(접근) 속도가 빠르다

한계

• 삽입, 삭제 시 오버헤드가 존재
• 크기를 변경하기가 어려움

문자열(string)

• 특별한 1차원 배열, char 형의 데이터들이 저장됨
• 해당 자료구조를 다루기 위한 함수들이 존재
  • c의 경우 길이 계산을 위한 strlen, 복사를 위한 strcpy 등

연결리스트

특징

• 데이터들이 노드라는 곳에 저장, 해당 노드들이 연결된 자료구조
  • 첫 번째 노드를 헤드, 마지막 노드를 테일이라고 부른다.
• 각 노드에는 데이터와 다음 노드를 가리키는 포인터가 담겨 있다.
• 배열과 달리 메모리 안에서 노드들의 물리적 순서가 리스트의 논리적 순서와 일치할 필요 없음
• 형태에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트로 구분
• 삽입, 삭제에 매우 용이

한계

• 구현이 복잡하여 오류가 발생하기 쉬움
• 임의 접근이 불가능

스택, 큐, 덱

스택(Stack)

특징

• LIFO(Last In First Out) 형태를 따르는 자료구조
  • LIFO(Last In First Out): 가장 최근에 들어온 데이터가 가장 먼저 나감
• 가장 위의 데이터만 접근할 수 있음(스택의 가장 상단을 top이라 함)
• push 연산을 통해 스택에 데이터를 추가, pop 연산을 통해 스택에서 데이터를 추출
• 앞선 배열, 연결 리스트를 이용해 구현
  • 배열의 경우: 구현이 간단, 크기가 제한
  • 연결리스트의 경우: 구현이 복잡, 크기가 제한되지 않음

한계

• 탐색을 하려면 원소를 일일히 다 꺼내야함

큐(Queue)

특징

• FIFO(First In First Out) 형태를 따르는 자료구조

  • FIFO(First In First Out): 먼저 들어온 데이터가 먼저 나감

• 가장 앞의 데이터만 접근할 수 있음

  • 큐의 가장 앞부분을 front, 가장 뒷부분을 back(rear) 이라 함

• enqueue(push) 연산을 통해 큐의 뒷부분에 데이터를 추가, dequeue(pop) 연산을 통해 큐의 앞부분에

  데이터를 추출

• 형태에 따라 선형 큐, 원형(환형) 큐로 구분

• 앞선 배열, 연결 리스트를 이용해 구현

한계

• 탐색을 하려면 원소를 일일히 다 꺼내야함

덱(Deque: Double Ended Queue)

특징

• 큐의 확장된 형태, 큐의 front와 back 양단에서 enqueue(push)와 dequeue(pop)연산이 모두 가능한 자료구조
• 앞선 배열, 연결 리스트를 이용해 구현