Array list와는 다르게 엘리먼트와 엘리먼트 간의 연결을 이용해서 리스트를 구현하는 것을 의미한다. 연결 리스트에서는 엘리먼트를 노드 또는 버텍스라고 부른다.
연결 리스트는 데이터와 다음 노드의 주소를 담고 있는 노드들이 한줄로 연결되어 있는 선형적인 데이터 방식의 자료구조다. Linked list의 최대 장접은 바로 데이터를 삽입하고 삭제하기 쉽다는 것이다. 대신, linked list에서 특정 위치의 데이터를 검색하기 위해서 첫 노드부터 탐색을 시작해야 한다. 그 시간이 O(n) 만큼 걸리기 때문에 탐색에 있어서 배열, 또는 트리 구조에 비해 느리다.
노드의 기본 구조를 살펴보면 더욱 이해가 될 것이다.
head는 건물의 출입문과도 같다. linked list를 사용하기 위해서는 head가 가르키는 첫번째 노드는 찾아야 한다. 왜? linked list는 특정 위치의 데이터를 찾을 수 없다. 첫 노드부터 탐색해야 하기 때문이다. 즉 head를 찾는 것이 매우 당연하고 중요하다!
데이터필드는 value라는 이름의 변수, 링크필드는 next 변수를 사용한다. value에는 노드값이 저장되고 next에는 다음 노드의 포인터, 또는 참조값을 저장해서 노드와 노드를 연결시킨다.
array list와 가장 차이점이 나타나는 부분이다. 배열은 중간 추가, 삭제할 경우 해당 엘리먼트의 뒤에 있는 모든 엘리먼트의 자리를 이동시켜야 했지만, linked list의 경우 추가/삭제가 될 엘리먼트의 이번, 이후 노드의 참조값(next)만 변경하면 되기 때문에 속도가 빠르다.
2번째 자리에 추가하고 싶다고 가정했을 때:
1. head를 참조해서 첫번째 노드를 찾아야 함
2. 첫번째 노드의 다음 노드(두번째)를 변수에 저장함
3. 두번째 노드의 다음 참조값도 변수에 저장함
4. 새로운 노드 생성함
5. 첫번째 노드의 다음 참조값으로 새로운 노드를 할당함
6. 새로운 노드의 다음 참조값으로 두번째 노드를 할당함
그럼 자연스럽게:
첫번째 노드 -> 새로운 노드 -> 두번째 노드
데이터를 추가하는 방식과 매우 비슷하다.
3번째 자리를 삭제하고 싶다고 가정할 때:
1. head를 참조해서 첫번째 노드를 찾음
2. 두번째 노드로 이동함
3. 세번째 노드를 찾음
4. 두번째 노드의 다음 참조값(next)를 네번째 노드로 변경함(.next.next)
5. 세번째 노드를 지움(delete)
linked list의 경우 head가 가르키는 노드부터 시작해 순차적으로 노드를 찾아가야 한다. 그러나 array list는 해당 엘리먼트에 바로 접근할 수 있다.
Reference:
https://opentutorials.org/module/1335/8821
https://underflow101.tistory.com/3
https://daimhada.tistory.com/72