node
-
[CS] Graph, TreeComputer Science/CS 2022. 11. 28. 18:44
트리 ⊂ 그래프 그래프 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 순환 혹은 비순환 구조를 이룬다. 그래프의 구현 방법은 2가지 방식이 있습니다. - 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식 - 인접 리스트(adjacency list) : 리스트를 사용하는 방식 두 방식의 메모리와 속도 차이는 다음과 같습니다. V : 노드의 개수, E : 간선의 개수 일 때, 인접 행렬은 O(v^2), 인접 리스트는 O(E) 만큼의 메모리 공간이 요구됩니다. 인접 행렬은 O(1), 인접 리스트는 O(V)만큼의 시간이 소요됩니다. 트리 그래프와 같이 노드와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 ..
-
[자료구조] Linked list (연결리스트)Computer Science/Data Structure 2022. 9. 23. 21:11
Linked List 란? node라는 객체로 이루어져 있다. 여러개의 node를 연결함으로써 데이터 표현 가능 시작(주소) - 연결(link) - 끝(null pointer or circular) 코드로 아래와 같이 구현할 수 있다. typedef struct Node{ int data; Node *next; }Node; Linked list 장점 동적으로 메모리 사용가능 메모리 효율적 사용 데이터 재구성 용이 대용량 데이터 처리 적합 Linked list 단점 특정 위치 데이터 검색 느림 메모리를 추가적으로 사용해야 함 Singly Linked list Circularly Linked list : 마지막 노드가 다시 처음 노드를 가리킴.