반응형 Computer Science/자료구조11 연결리스트와 선형 자료구조 (1) 이번 포스트에서는 저번 포스트에서 설명드린 선형 자료구조들을 배열이 아닌 연결리스트로 구현하는 내용에 대해 소개하도록 하겠습니다. 먼저 구현을 위해 연결리스트의 종류와 구현에 대해서 설명드리겠습니다. 연결리스트의 종류 연결리스트는 크게 단방향 연결리스트와 양방향 연결리스트로 나뉘어져 있습니다. 단방향 연결리스트는 이름대로 방향이 한쪽으로만 존재하기 때문에 뒤쪽 노드의 정보를 알 수 없습니다. 반대로 양방향 연결리스트는 앞, 뒤쪽 노드에 접근이 가능합니다. 연결리스트의 구현 단방향 연결리스트에서 각 노드는 데이터 값과, 다음 노드를 가리키는 포인터를 가집니다. 그리고, 연결리스트의 제일 첫번째를 가리키는 head 포인터가 존재합니다. 이 포인터는 초기값을 NULL로 지정하여 공백리스트임을 표시합니다. 1 .. 2023. 8. 1. 선형 자료구조 (스택, 큐, 덱) 스택 [이 포스트에서는 라이브러리를 사용하는 자료구조가 아닌 배열을 사용하여 자료구조를 다루고 있습니다.] 스택은 스택에 값을 삽입하는 push()와 값을 삭제하는 pop(), 스택이 비었는지 확인하는 isEmpty(), 스택이 포화상태 인지 확인하는 isFull() 정도로 기능을 설명할 수 있습니다. 또, 스택에는 top이라고 불리는 포인터가 있습니다. 이 포인터는 현재 스택의 최상위 값을 나타내며, 이 포인터가 배열의 끝을 가리키고 있다면 포화상태 즉, Full이라고 할 수 있고 배열의 제일 첫번째를 가리킨다면 Empty라고 할 수 있습니다. 1 2 3 4 5 6 7 8 9 10 11 //배열의 사이즈는 N으로 정의 bool isFull() { if(top == N - 1) return true; r.. 2023. 7. 6. 자료 구조(Data Structure)의 개념과 종류 자료구조 프로그램을 구성하는데 있어 자료구조와 알고리즘을 필요로 합니다. 자료구조란 자료에 대한 효율적 탐색, 삽입, 삭제 등이 가능하도록 자료들을 구조화 해둔 것을 의미합니다. 알고리즘은 문제를 처리하는 절차로, 기술하는 방법에 있어서는 자연어, 흐름도(순서도), 의사코드, 프로그래밍 언어로 구분할 수 있습니다. 자료구조는 추상자료형에 따라 다르게 구현될 수 있습니다. 여기서 추상자료형(Abstract Data Type, ADT)이란, 자료에 대한 정의 혹은 자료에 대해 가능한 연산에 대한 정의로 볼 수 있습니다. 추상 자료형 표현하는 자료 구현 자료구조 리스트 (List) 순서가 부여된 자료 모음 배열 (Array) 연결리스트 (Linked List) 스택 (Stack) 후입선출 (LIFO) 방식으로.. 2023. 7. 4. 이전 1 2 3 다음 반응형