개요
연결 리스트란 요소를 차례차례 연결시켜서 만든 리스트형 자료구조다. 배열 리스트(ArrayList)와 다른 점은, 연결 리스트는 구현에 배열을 사용하지 않았다는 것이다.
연결 리스트에서 요소를 삽입하면, 배열의 특정 위치에 요소를 저장하는 대신 노드(Node)라는 곳에 저장한다. 이 노드라는 것은 마치 열차 칸과 같은데, 자신의 이전, 다음 순번을 가리키는 연결고리(Link)를 같이 가지고 있어서 마지 쇠사슬을 엮는 듯이 서로 얽히는 구조를 띄도록 만든다.
이런 특수한 구조로 인해 다음과 같은 특징을 가진다.
특징
배열 리스트에 비해 삽입과 삭제가 빠르다
배열 리스트는 배열의 크기가 수시로 변하는 것처럼 보이지만, 사실 내부에서는 고정된 배열에 요소를 삽입/삭제하고 있다. 그러다가 요소가 배열의 크기를 넘어서면, 새로운 크기의 배열을 만들고 거기에 이전 배열에 있던 내용을 전부 복붙한다. 그렇기에 삽입을 할 때 중간에 턱하고 프리징이 걸리는 구간이 생긴다. 삭제를 할 때는 삭제한 요소 뒤의 요소들을 전부 앞으로 끌어온다. 그렇기에 연산을 상당히 잡아먹는다.
연결 리스트는 배열을 쓰지 않는다는 이점으로 인해 그런 걱정을 하지 않아도 된다. 그냥 새로운 노드를 만들어서 맨 뒤의 노드와 연결만 시켜주면 되기 때문이다. 삭제를 할 때에도 삭제한 노드의 이전 노드와 다음 노드를 연결시키기만 하면 된다. 배열에 비하면 엄청 빠른 셈.
다만 이런 장점에 비해 단점이 꽤 있는데...
저장 순서가 비연속적이라 검색 속도가 느리다
배열 리스트의 경우 요소를 배열에 순서대로 저장한다. 그렇기에 인덱스를 통한 빠른 접근이 가능하다.
하지만 연결 리스트는 요소를 노드에 저장한다. 이 노드는 광활한 데이터 공간 중 아무 위치에나 만들어지기 때문에, 인덱스를 사용할 수 없다. 무조건 첫번째부터 차례차례 순회해야 한다는 뜻이다. 따라서 원하는 위치로 바로 접근할 수가 없으며, 심지어 일반적인 순회 연산도 배열 리스트보다 불리하다.
배열 리스트의 경우: 0번 요소 접근 -> 대조 -> 1번 요소 접근 -> 대조 -> ...
연결 리스트의 경우: 0번 노드 접근 -> 노드의 요소에 접근 -> 대조 -> 다음 노드에 접근 -> 노드의 요소에 접근 -> 대조 -> ...
참조를 두 번, 게다가 메소드를 통해서 해야하므로 검색에는 무리가 있는 편.
노드의 크기만큼 메모리 할당량이 증가한다
노드가 가진 링크 때문에, 요소 외에도 데이터가 좀 더 늘어나게 된다. 링크를 int형 포인터 변수라고 생각한다면 이전 링크, 다음 링크 두 개의 변수에 총 8byte를 쓰는 셈인데, 요소의 크기가 4byte라면 배보다 배꼽이 더 큰 상황이 될수도 있다.
말이 쉬워서 8byte지, 리스트의 길이가 100만이 되면 약 7.6mb를 더 쓰게 되는 셈이다.
주요 메소드
기본적으로 다음과 같은 기능을 가진다.
addFirst(), addLast(), add(인덱스, 요소)
리스트의 처음이나 끝에 요소를 추가한다.
인덱스를 넣을수도 있는데, 이러면 처음에서 인덱스 수만큼 건너뛰어서 요소를 추가한다.
removeFirst(), removeLast(), remove(인덱스, 요소)
리스트의 처음이나 끝의 요소를 제거한다.
get(인덱스), set(인덱스, 요소)
특정 위치의 요소를 가져오거나, 다른 요소로 대체한다.
어떤 때에 쓰이나
위에 설명했듯, 데이터의 삽입, 삭제가 빈번할 때 사용할 수 있다. 배열 리스트는 O(n)의 시간이 걸리지만, 연결 리스트는 O(1)로 훨씬 빠르기 때문이다.
데이터의 순서 변경이 빈번할 때에도 사용할 수 있다. 배열 리스트는 데이터가 배열에 귀속되어 있기 때문에 순서를 바꾸면 다른 요소들까지 영향을 받게 된다. 하지만 연결 리스트는 그냥 떼서 갖다 붙이는 형식이라 훨씬 빠르고 온전하게 순서를 바꾸는 게 가능하다. (그와 반대로 정렬은 불리할 수 있다.)
다른 자료 구조의 구현에 사용되기도 한다. 예를 들어 큐나 스택은 배열보다는 연결 리스트로 구현하는 것이 훨씬 간편하다. (특히나 원형 큐, 이진 탐색 트리 등!!)
