연결 리스트 (LinkedList)

연결 리스트(LinkedList)는 서로 떨어져 있는 메모리 공간을 포인터를 사용해 연결시켜 놓은 자료 구조이다. 

배열리스트는 배열(Array)를 이용하기 때문에 처음에 정해 놓은 메모리 공간에서 벗어날 수 없지만(지정해놓은 배열의 최대 크기를 벗어날 수 없다) 연결 리스트(LinkedList)는 그런 한계 없이 자유롭게 노드를 추가할 수 있다. 

물리적 메모리 공간에서, 배열 리스트와 연결 리스트가 메모리를 점유한 모습이다. 배열 리스트는 배열을 사용해 순차적으로 메모리 공간을 사용하지만, 연결 리스트는 그렇지 않다는 점을 보여준다.

연결 리스트는 포인터를 사용하기 때문에 데이터를 빈번하게 삽입, 삭제해야 하는 상황에서 상당히 유연하게 움직인다. 해당 노드의 링크만 연결해주고, 끊어주면 되기 때문에 삽입, 삭제 위치 옆에 있는 원소들을 모두 이동시켜 줘야 하는 배열 리스트와는 속도 차이가 많이 난다. 

다만 인덱스(index) 값을 사용해 접근하지 않기 때문에, 검색에는 느리다는 단점도 있다. 

해당 노드로 이동하기 위해서는 노드 간에 포인터를 타고 가야 한다는 점 때문에 이동 속도가 느리다. 

또한 상대적으로 구현 복잡도 또한 올라간다. (물론 고수의 경우는 예외다)

구현하려는 목적에 따라서, 추가 삭제보다는 검색이 자주 사용된다면 배열 리스트를 쓰고 그 반대라면 연결 리스트를 사용하는 것이 적절하다고 볼 수 있다.

연결 리스트의 가장 기본적인 구조는 이와 같다. 리스트의 요소 하나를 노드(Node)라고 부르는데, 구조체로 만들어 진다. 여기에는 데이터를 저장하는 부분과 다음 노드를 가리키는 포인터가 들어있다.

연결리스트의 종류는 3가지가 있다.

1. 단순 연결 리스트(Simple Linked List) 

2. 원형 연결 리스트 (Circular Linked List)

3. 이중 연결 리스트 (Doubly Linked List)

원형 연결 리스트의 경우 끝으로 이동하면 다시 노드를 탐색할 수 있는 장점이 있고

이중 연결 리스트의 경우 2개의 포인터가 각각 이전 노드와 다음 노드를 가리키고 있어 앞 뒤로 자유롭게 이동할 수 있다는 장점이 있다.

이 3가지 중에 자신이 구현하려는 것에 가장 적합한 것을 골라서 사용하면 된다.