목록singly (1)

N

(TIL Day03-02)자료구조-연결 리스트(1) 단방향 연결 리스트

연결 리스트 각 요소를 포인터로 연결하여 관리하는 선형 자료구조. 각 요소는 노드라고 부르며, 데이터 영역과 포인터 영역으로 구성된다. 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다. 탐색은 O(n)이 소요. 요소를 추가하거나 제거할 때는 O(1)이 소요. Singly Linked List, Doubly Linked List, Circular Linked List가 존재. 배열과의 차이점 배열은 데이터가 메모리에 연속적으로 붙어있지만, 연결 리스트는 붙어있지 않다. 원소를 찾기 위해서 배열은 인덱스로 접근이 가능하지만, 연결 리스트는 해당 데이터 영역을 찾아야 한다.(그렇기 때문에 에 시간 복잡도가 서로 상반된다.) Singly Linked List 단방향 연결 리스트 Head에서 Tail까지 단..
TIL 2021. 8. 5. 11:05
이전 Prev 1 Next 다음