자료구조
자료구조는 데이터의 표현 및 저장 방법을 의미한다.
자료구조의 종류에는 Array list, Linked list, Stack, Queue 등이 있다.
리스트라는 어떤 기능을 가지고 있는 data structure을 만드는 여러가지 방법 중에 Linked list에 대해서 먼저 알아보자 !
Linked list
Array list와 다르게 엘리먼트와 엘리먼트 간의 연결을 이용해서 리스트를 구현한 것이다. 
위 그림처럼 한 곳에 가지런히 모여 있는 Array list와 달리 Linked list는 엘리먼트들이 떨어져 있는 모습을 볼 수 있다. 
위치가 흩어져있는 각 엘리먼트들은 연결되어 있다.
어떤 구조로 연결되어 있을까?
위 그림은 단방향 linked list의 구조에 대한 시각화 자료이다. 리스트는 노드(엘리먼트)들의 모임이며 각 노드는 변수가 저장되는 Data field, 다음 노드의 참조값(주소)을 저장하여 알려주는 Link field로 구성되어 있다.
리스트의 출입문 역할을 하는 head는 linked list를 사용하기 위해 찾아야 하는 첫 번째 노드이다.
linked list에서는 새로운 노드를 시작부분에 추가, 중간에 추가, 삭제하는 활동 등을 구현할 수 있다.
Array list vs Linked list
-
엘리먼트의 추가, 삭제 : Array list < Linked list
-
특정 인덱스 조회 : Array list > Linked list
Doubly linked list (이중 연결 리스트)
단방향으로 연결된 단방향 연결 리스트의 단점을 보완하기 위한 이중 연결 리스트도 존재한다. 그림과 같이 각 노드가 Previous와 Next로 구성되어 있다. 양방향으로 연결되어 있기 때문에 노드를 탐색하는 방향이 양쪽으로 가능하다. 특정 인덱스 위치의 엘리먼트를 가져오는데에 장점이 분명하다.
하지만 단점은 previous에 변수를 하나 더 사용해야 하기 때문에 메모리를 더 많이 사용해야 하고 단방향 링크 리스트보다 구현하기에 더 복잡하다.
장점이 크기 때문에 현실에서는 양방향 링크 리스트를 자주 사용한다.
참고
