목록2022/09/06 (1)

넘치게 채우기

[자료구조] 1-2. 연결 리스트(Linked List)

연결 리스트는 순차 리스트와는 다르게, 리스트의 노드(요소)값의 메모리주소가 순차적이지 않다. 대신, 노드에 자신의 값과, 다음 노드의 메모리주소를 저장한다. 시작하는 노드를 머리(head)라고 하고, 맨 끝을 꼬리(tail)이라고 한다. 노드에서 다음 노드로 향하는 주소값을 포인터((Pointer)라고 한다. tail노드에서 가지고 있는 포인터값은 none 또는 null이라 한다. 접근 [2]에 있는 값을 보려면, 머리부터 다음 노드를 하나하나 찾아가야한다.(순차적으로 탐색해야한다) 시간복잡도는 O(N)이다. 삽입 A - B - C로 연결되어있는 연결 리스트 중 B-C 사이에 D 노드를 삽입하고 싶으면, B의 포인터를 D의 메모리주소, D의 포인터를 C의 메모리주소로 바꿔주면된다. 이때, 바꾸는 것의 ..
컴퓨터과학/자료구조 2022. 9. 6. 23:02
이전 Prev 1 Next 다음