-
LinkedList자료구조 2021. 9. 10. 12:20
LinkedList 란?
LinkedList에 대한 설명은 이전에 정리해놓은 글을 참고하자.
https://hyokeun0419.tistory.com/25?category=888578
LinkedList 구현
header 가 삭제되었음에도 이 후 노드들이 계속해서 header 의 주소값을 가지고 있으면 안된다.
이 문제를 쉽게 해결하기 위해 LinkedList 클래스 안에서 Node 클래스를 구현하고 header 를 데이터가 아닌 LinkedList 의 시작을 알려주는 용도로 구현하였다.
class LinkedList { Node header; static class Node { int data; Node next = null; } LinkedList() { header = new Node(); } void append (int d) { Node end = new Node(); end.data = d; // 여기서 header는 관리용도로만 쓰이고 있다. (데이터가 없음) Node n = header; while (n.next != null) { n = n.next; } n.next = end; } void delete (int d) { // 여기서 header 관리용도로만 쓰이고 있다. (데이터가 없음) Node n = header; while (n.next != null) { if (n.next.data == d) { n.next = n.next.next; } else { n = n.next; } } } void retrieve() { // header는 관리용도로만 쓰이고 있기 때문에 헤더 다음부터 데이터를 꺼내온다. Node n = header.next; while (n.next != null) { System.out.print(n.data + " -> "); n = n.next; } System.out.println(n.data); } } public class Main { public static void main(String[] args) { LinkedList ll = new LinkedList(); ll.append(1); ll.append(2); ll.append(3); ll.append(4); ll.append(5); ll.retrieve(); ll.delete(1); ll.retrieve(); } }
참고자료
https://www.youtube.com/watch?v=DzGnME1jIwY&list=PLjSkJdbr_gFZQp0KEoo0Y4KkCI5YqxtjZ
'자료구조' 카테고리의 다른 글
그래프(Graph) 설명과 DFS, BFS 구현 (0) 2021.10.30 트리(Tree) 설명과 구현 (0) 2021.10.30 ArrayList & LinkedList 설명과 비교 (0) 2021.08.21 HashTable (0) 2021.08.21