해나의 컴공생존기

Linked List 연속적인 노드 Node : unit of storage (item) Nodes are linked with pointers Linked list는 배열과 다르게 메모리 아무데나 있을 수 있다. 대산 한 노드에 가면(=한 노드의 주소를 알아서 그곳의 내용을 읽으면) 다음에 갈 노드의 주소가 적혀있다. 즉 노드들이 포인터들도 연결이 되어 있는 것이다. Linked List의 노드의 구조를 살펴보면 다음과 같다. Whole List 이런식으로 구성이 되어있다. (화살표 등은 사람이 보기 쉽게 표현한것이다.) 마지막 노드에는 더이상 갈 곳이 없으므로 null값을 넣는다. 첫번째 노드로 갈때는 어쩔수 없이 그 노드가리키는 포인터를 가지고 있어야 한다. Code for List class No..

대부분의 자료구조는 Search, Insert, Delete가 중요하다. 오늘은 배열의 Search, Insert, Delete 를 보려고한다. 배열 상태에 따라 방법이 달라진다 Packed vs Unpacked : 빈자리가 있나 없나 Sorted vs Unsorted : 정렬이 되어있나 없나 총 4가지 경우를 보려고 한다. Case 1 ) Packed, Unsorted 가장 간단한 방법 Item의 개수를 표시하는 변수가 따로 필요 하다. => 위 배열을 보면 item이 5개 있으니 어딘가에 5라고 저장 해놓으면 해결된다. Search : n개의 배열에서 어떤 값 x가 있는지 없는지 확인, O(n) Insert : [Search, O(n)], O(1)(상수시간) Delete : [Search, O(n)]..