자료구조3 Circular Linked List(원형 연결 리스트) (Java) Circular Linked List는 Singly Linked List(단일 연결 리스트)의 확장된 개념이다. 나는 단일 연결 리스트의 끝 원소(꼬리, tail)를 가장 앞 원소(머리, head)로 이어줌으로써 선형의 리스트가 둥글게 말리는 효과를 얻는다고 이해했다. 그래서 내가 이해한 바를 토대로 오늘 구현을 시작했다. 장점 효율적인 탐색 : 원형 연결 리스트의 어느 부분에서 시작하던, 모든 노드(원소)들을 탐색할 수 있다. 단점 메모리 사용량 : 마지막 노드(원소)가 처음 노드를 가리키기 때문에 약간의 메모리를 더 사용한다. 무한 루프 : 마지막 노드가 처음 노드를 가리키기 때문에 조건 등을 걸지 않고 탐색하면 무한 루프에 빠질 수 있다. 삭제 코드의 복잡성 : head나 tail 노드의 경우, 삭.. 2023. 3. 24. Doubly Linked List(이중 연결 리스트) (Java) Doubly Linked List는 Singly Linked List(단일 연결 리스트)의 확장된 개념이다. 단일 연결 리스트는 맨 처음 노드에서 맨 끝 노드로 순차적으로 이동하면서 원하는 정보를 담은 노드를 탐색할 수 있다. 하지만 반대로 맨 뒤에서 앞으로는 탐색이 불가능하다. 왜냐하면 노드가 자신의 앞 노드의 정보를 가지고 있지 않기 때문이다. 반면, 이중 연결 리스트는 뒤에서 앞으로도 탐색이 가능하다. 단일 연결 리스트의 각 노드에 앞 노드의 정보를 추가해주는 작업을 더해주면 이중 연결 리스트를 구현한 것이다. 장점 이중 연결 리스트의 장점은 탐색에서 드러난다. 원하는 노드가 어느 위치(index)에 있는지도 알고 있다면, 노드의 위치를 리스트의 길이의 반과 비교해서 더 빠르게 탐색할 수 있는 지점.. 2023. 3. 22. Singly Linked List(단일 연결 리스트) (Java) 새로운 노드를 insert할 때마다, 이전에 있던 노드들과 새 노드를 대소 비교한다. 그러면서 더 큰 값이 start(head)와 가깝게, 즉 내림차순으로 list를 형성한다. package LinkedList; public class SinglyLinkedList { class Node { int data; Node next; Node(int data) {this.data = data;} Node(int data, Node next) { this.data = data; this.next = next; } } int size = 0;// 연결 리스트에 저장된 원소의 개수 Node start = null; //연결 리스트를 가리키는 레퍼런스 , start == head // x를 list에 내림차순으로 삽.. 2023. 3. 21. 이전 1 다음
