Dog foot print

기존에 만들어서 올린 완전이진트리는 node타입이 마지막 삽입을 위한 노드에 대한 정보를 가진 링크가 더 있어서 구조체가 최소화 되지 못했다고 생각한다. 그래서 기존에 만든 완전이진트리의 노드는 node + queue의 역할을 겸하기에 이번에는 따로 분리 해주었다. 이번 작업에서는 queue를 이용한 트리에서 마지막 삽입된 노드를 찾는 흐름과 마지막 삽입된 노드의 부모를 찾는 작업의 흐름, 삽입되어야 할 위치를 찾기 위한 흐름을 보기위해서 삽입과 삭제시마다 queue를 새로 생성해서 찾게 하였다. 만약 적은 움직임으로 찾게 하고 싶으면, 트리의 선형적인 구조를 담은 queue를 어딘가 보관하고, 삭제할 노드의 부모노드에 대한 정보를 알고 있어야 한다. 구조 // tree -> node typedef st..

지난번 만들어 보았던 단순연결리스트는 마지막 node 가 null을 가리키고 있는 형태를 하고 있는데 오늘 만들어볼 원형 연결리스트는 마지막 노드가 항상 Head 노드를 가리키고 있어 노드의 링크를 타고 다시 처음으로 갈 수 있다는 이점이 있다. // 아직 원형연결리스트가 단순연결리스트보다 더 좋은 이점을 찾지를 못 찾겠다. 루프를 만들어 내부에 뭐가 있는지 순차적으로 감시하기에는 좋을 듯 하다. 원형연결리스트 필요한 멤버 변수 처음 만들어지는 head는 data로 head가 들어간다. constructor(item){ this.data = item; this.link = null; } 필요한 메서드 insertFirstNode(item) // node를 생성하고 head바로 앞에 넣는다. insertL..

javascript의 배열은 array-list라는 것의 형태를 띄고 있어 배열의 크기 존재하지 않는다. 그런데 c 같은 언어들은 배열의 크기가 존재하기에 한 배열을 유한하게 밖에 사용 할 수 없다. 그래서 개발자들은 노드리스트라는 개념을 만들어 각각의 구조체들로 서로를 연결하는 것을 만들었다. 연결리스트에는 단순 연결리스트, 이중연결리스트, 원형연결리스트가 있으며 이 연결리스트들을 이용하여 스택, 큐, 트리등 다양한 자료구조를 만들 수 있다. node 란 node란 data필드와 link필드를 가지고 있는 일종의 구조체로 link를 통해서는 다음 연결된 노드에 접근 할 수 있다. simple linked-list는 처음 노드를 header라고 하며 마지막 노드의 link는 항상 null이다. 연결리스트..