[자료구조 학습] 1. Linked List 정리

알고리즘 풀이

르라나 2020. 12. 4. 22:40

- 일단 리스트란, 데이터를 일직선으로 나열한 형태. 데이터의 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸린다.

- 리스트에서는 데이터가 메모리상의 연속된 위치에 저장하지 않아도 되며, 보통 떨어져 있음.

- 흩어져 저장되어 있으므로 포인터를 처음부터 순서대로 따라가야만 원하는 데이터 접근 가능.

- 데이터 추가는 추가할 위치의 앞뒤 포인터를 변경만 하면 되므로 간단하다.

2. Linked List는 List의 구현체

- 일반적으로 그 구조체와 포인터로 구현된다.

- 다음 노드의 주소가 하나라도 잘못되면 전체를 못쓰기 때문에 안정적인 구조는 아니다.

나무위키에 설명이 잘 되어 있다.

연결 리스트 - 나무위키

배열과는 달리 첫번째 데이터의 추가/삭제가 O(1)의 시간안에 수행된다. 배열의 경우 데이터를 추가 또는 삭제할 때 해당 지점 뒤쪽의 데이터를 모두 이동해야 하나 연결 리스트는 그럴 필요가

namu.wiki

Linked list - Data Structure (자료구조)

소개 Linked List는 Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미합니다. 그래서 이름도 linked list입니다. 그렇게 보면 linked list에서 가장 중요한

opentutorials.org