Linked List (1) 썸네일형 리스트형 Chapter2 Linked Lists Createing a Linked ListLinkedList는 각 노드마다 다음 노드의 주소값을 가지고 있는 List입니다. 배열처럼 인덱스를 가지고 탐색하는것이 아니고 연결된 리스트를 하나하나 탐색하며 찾다보니 탐색에 대한 시간복잡도는 O(n)입니다. 대신 삽입/삭제 연산시에는 배열은 Shift하는 과정이 필요해서 복잡도가 O(n)이지만 LinkedList는 해당 노드의 앞뒤의 연결부분만 바꿔주면 되기 때문에 상수시간의 복잡도로 처리가 가능하다는 장점을 가지고 있습니다. 중간에서 삭제를 하거나 삽입을 하는 경우엔 케이스를 나눠서 구현하면 쉽게 구현할 수 있다. 헤드가 타겟 노드인 경우타겟노드가 중간에 있는 경우리스트의 마지막 노드가 타겟 노드인 경우때문에 위의 코드처럼 3가지 경우를 나눠서 연결 상태를.. 이전 1 다음