Computer Science & Engnieering/data structure5 [자료구조] 연결 리스트(Linked List) 연결 리스트(Linked List)란?연결 리스트(Linked List)는 데이터를 저장하는 노드(Node)들이 포인터를 통해 연결된 자료구조입니다. 순차 자료구조인 배열(array)은 탐색 속도는 빠르지만, 삽입이나 삭제 연산 시 기존 원소를 옮겨야 하므로 시간이 더 소요됩니다. 이러한 단점을 보완하기 위해, 데이터를 저장하는 노드(Node)들이 포인터로 연결된 자료구조인 연결 리스트(Linked List)가 사용됩니다. 예를 들어연결 리스트는 기차에 비유할 수 있습니다. A, B, C라는 칸이 있고 다음칸을 나타내는 번호표가 있다면 A칸 다음 번호표가 B칸이라면 A칸과 B칸은 연결됩니다. 그리고 B칸은 C칸을 C칸은 X라는 번호표라면 B칸은 C칸과 연결되고 C칸은 마지막 칸이 됩니다. 기차의 칸을 연.. 2024. 11. 12. 트리 트리의 이해트리는 리스트, 스택, 큐와 같은 1:1 관계의 선형구조가 아닌 1:N 관계의 비선형, 계층형 자료구조입니다.트리의 구조와 구성 요소도는 위에 그림과 같습니다. 트리를 구성하는 원소(자료)를 노드라 하며 노드Node를 연결하는 선을 간선Egde이라고 합니다.그림 속 트리의 노드가 A, B, C, D, E, F, G, H, I, J, K, L로 12개 있고 부모 노드와 자식 노드는 간선으로 연결되어 있습니다.트리의 시작 즉 A를 루트 노드라 하며 자식 노드와 연결됩니다. 같은 레벨에 있는 노드를 형제 노드라 합니다.조상노드는 루트노드 까지의 경로로 K의 조상 노드는 F, B, A가 됩니다. 노드의 차수는 자식 노드의 개수를 의미합니다. 자식 노드가 없는 즉 차수가 0인 노드를 단말 노드라 합니다.. 2024. 8. 29. 스택 스택의 이해스택의 개념과 구조스택 자료구조는 지층이 쌓이듯 데이터를 차곡 쌓아올린 형태로 자료를 구성합니다.예를 들어 프링글스처럼 통안에 들어있는 감자칩과 비슷한 개념이라고 볼 수 있습니다. 스택은 정해진 방향으로 데이터가 입력되고 top은 새로 입력된 데이터를 가리키게 새로 갱신됩니다. 따라서 top은 항상 가장 마지막에 들어온 데이터를 가리키게 됩니다.스택은 top으로 정한 곳에서만 삽입과 삭제가 이루어지기 때문에 가장 마지막에 들어온 데이터가 가장 먼저 삭제된다는 후힙선출(Last-In-First-Out) 동작 구조를 가집니다.스택의 동작 방식은 위에 사진과 같습니다.push를 실행하면 top 위치에 데이터가 들어가고 top은 1이 증가하게 됩니다. pop의 경우에는 top 위치 데이터를 삭제하고 .. 2024. 8. 28. 순차 자료구조와 연결 자료구조 순차 자료구조 자료는 구조화하는 방법에 따라 리스트, 스택, 큐, 데크, 트리, 그래프 등으로 나뉩니다. 이러한 자료구조를 구현하는 방식에는 순차 자료구조와 연결 자료구조가 있습니다. 순차 자료구조는 구현할 자료를 논리적인 순서대로 메모리에 연속해서 저장하는 방식입니다. 그래서 순차 자료구조는 논리적인 순서와 물리적인 순서가 일치해야 합니다. 연결 자료구조 순차 자료구조는 논리적 순서와 물리적 순서가 같기 때문에 찾는건 매우 빠르지만 삽입 삭제 연산을 하면 물리적 순서와 논리적 순서를 일치 시키기 위해 원소를 옮기는 작업이 필요해 그 만큼 시간이 필요합니다. 연결 자료구조는 원소의 물리적 순서와 논리적 순서가 일치하지 않아도 됩니다. 따라서 원소를 옮기는 작업이 필요없게 되어 순차 자료구조보다 삽입 .. 2024. 8. 28. [자료구조] 배열(Array) 배열 (Array)이란?배열(Array)은 자료형이 같은 데이터 요소들을 연속적으로 메모리에 저장하는 자료 구조입니다. 예를 들어계절 봄, 여름, 가을, 겨울로 각각의 변수로 선언하면 개별적으로 변수를 만들어 사용해야 합니다. 하지만 배열로 묶어서 만들면 배열을 한 번만 선언해 만들 수 있고, 배열의 요소가 되므로 다루기 편해집니다. 배열의 요소를 구별하기 위해 인덱스를 사용하고 배열의 요소를 사용할 때는 배열 이름[인덱스] 형식으로 사용합니다. 배열 사용 시 주의 사항으로는1. 배열의 인덱스는 0부터 시작합니다. ● 예를 들어, int arr[5]; 라는 배열의 인덱스 범위는 0 ~ 4 입니다.2. 배열의 크기를 초과한 인덱스 접근은 오류를 발생시킵니다. ● C언어에서는 경고 없이 메모리 침.. 2024. 8. 28. 이전 1 다음
