Linked List에 대해 얘기하기 전에 먼저 List에 대해 이야기해보자.
List는 Array(배열)를 보완한 Data Structure라고 할 수 있다.
Array(배열)는 많은 양의 데이터를 한번에 모아 효율적으로 관리할 수 있는 Data Structure이다. 이런 배열의 가장 큰 특징 중 하나는 바로 Index의 존재이다. Index는 데이터의 순서를 나타내고 이를 이용해 효율적으로 데이터를 배열에서 호출할 수 있다. 하지만 반대로 말하면 데이터를 관리하기 위해 데이터마다 Index 값이 고정되어야 한다는 뜻이고 만약 어떤 데이터가 배열에서 삭제되면 그 Index는 빈공간으로 놓아두어야 한다.
이런 단점들을 보완하기 위해 List는 Index라는 개념을 과감히 배제한다. 대신 데이터를 넣을 때 빈틈없이 넣는다.
List에서는 Index가 없는 대신 Sequence라는 개념이 있다. 엘리먼트들 간의 순서인 것이다. 순서가 있지만 고정된 자리는 없는 Data Structure가 바로 List이다.
이런 List에는 두가지 유형이 있는데 Linear list(선형 리스트)와 Linked list(연결 리스트)가 그것이다. 오늘은 Linked list에 대해 알아보자.
Linked list (연결 리스트)
먼저 Linked list의 구조를 살펴보자
Linked list에서 각 요소는 위의 그림과 같이 데이터를 저장할 장소(DATA)와 다음 요소를 가리키기 위한 장소(NODE)로 구분되어있다. 그렇기 때문에 Linked list에서는 3번째 데이터로 가기 위해선 1번째, 2번째 요소를 거쳐야 갈 수 있다.
Method
append() : 리스트의 맨 끝에 요소를 추가한다.
getElement() : 현재 위치의 요소를 나타낸다.
insert() : 기존 요소 위에 새로운 요소를 추가한다.
remove() : 기존 요소를 삭제한다.
front() : 현재 위치를 리스트의 첫번째 요소로 설정한다.
end() : 현재 위치를 리스트의 마지막 요소로 설정한다.
prev() : 현재 위치를 한 요소 뒤로 이동한다. ex (3번째 요소 -> 2번째 요소)
next() : 현재 위치를 한 요소 앞으로 이동한다. ex (3번째 요소 -> 4번째 요소)
clear() : 모든 요소를 삭제한다.
Property
pos : 현재 위치를 보여준다.
length : 리스트 요소 수를 보여준다.
