Linked List란?
불연속으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다.
Linked List는 배열의 단점을 보완하기 위해 고안되었다.
Array는 가장 기본적인 형태의 자료구조로 간단하며 사용하기 쉽고 읽어오는 시간이 빠르지만
• 크기를 변경할 수 없고
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
위와 같은 단점이 있어, 메모리 낭비가 시간 소모가 있을 수 있다는 것이 단점이다.
Linked List의 link 구조
Linked List의 저장공간 구조는 위와 같다. ↑
Linked List의 데이터 삭제와 추가
Linked List의 각 요소(node)들은 자신과 연결된 다음 요소의 주소값 & 데이터값으로 구성되어 있다.
위와 같은 구조 덕분에 Linked List에서의 데이터 삭제와 추가는 간단하다.
1 2 3 4의 Linked List 구조에서 중간에 있는 값인 3을 삭제하려 한다면,
2가 가지고 있는 다음 연결 node의 주소값을 3의 것이 아닌 4의 주소값으로 변경하기만 하면 된다.
◦ 참조하는 주소가 없는 4의 저장공간은 GC에 의해 사라진다.
1 3 4의 Linked List 중간에 새로운 값인 2를 추가하려면,
1이 가진 다음 주소값에 2의 주소값을 넣고, 2의 주소값에 다음 node인 3의 주소값을 넣기만 하면 끝이다.
Linked List와 Array List의 차이 (Linked List의 장단점)
- 읽어오는 속도는 Linked List가 더 느리다.
- Array List는 데이터 저장공간이 연속적이기 때문에, 변수의 크기를 계산해서 원하는 요소의 주소를 얻어 다음 데이터의 주소값을 얻어올 수 있지만 Linked List는 데이터들이 불연속적으로 서로 연결만 되어있는 것이기 때문에, 차례대로 따라가야만 원하는 데이터의 주소값을 찾아낼 수 있다. 그래서 데이터의 개수가 많아질수록 접근시간 (Access Time)이 길어진다.
- 추가/삭제 시 속도 차이가 있다.
- 순차적으로 추가/삭제할 경우, Array List가 데이터의 재배치 할 필요없이 바로 삭제하기 때문에 Linked List보다 더 빠르다.
- 중간 데이터를 추가/삭제하는 경우, Linked List는 주소값만 바꿔주는 반면에 Array List는 추가/삭제 후 데이터 재배치를 하는 과정이 필요하기 때문에 Linked List가 더 빠르다.
Linked List 종류
Linked List는 다음 연결 node에 대한 주소값만 가지고 있기 때문에, 이전 node에 접근하기 어렵다.
이를 보완하기 위해
- doubly linked list : Linked List의 node에 이전 node의 주소값을 하나 더 추가한 것이다.
- doubly circular linked list : doubly linked list의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다.
가 있다.
'CS' 카테고리의 다른 글
| CS :: 배열 Array (0) | 2022.05.01 |
|---|