연결리스트란?
: 비연속적으로 많은 데이터를 저장하는 자료구조로 데이터가 저장된 노드, 노드의 순서를 연결한 링크로 구성된다.
연속적으로 많은 데이터를 저장하는 배열과 차이가 있다.
가장 첫 노드는 head이고 마지막 노드의 링크는 null이다.
연결리스트의 특징
연결리스트는 메모리상 연속성이 보장되지 않고 다음 노드를 저장하여 순서를 알 수 있다. 반면 배열은 메모리상 연속적이게 저장된다. 이로 인해 장단점이 생기는데,
장점
- 데이터 공간을 미리 할당할 필요 없다. 전체 크기를 미리 정하지 않고 그때그때 추가, 삭제에 용이하게 할 수 있다.
단점
- 링크를 저장하는 추가 공간 필요
- 접근 속도가 느림 (배열은 O(1), 연결리스트는 O(n))
자바 연결리스트
LinkedList<Integer> linkedList = new LinkedList<>();
// add(data), add(i, data) : 데이터 추가
linkedList.add(1); // [1]
linkedList.add(3); // [1,3]
linkedList.add(1,2); // [1,2,3]
// set(i, data) : i에 값 data로 변경
linkedList.set(1,4); // [1,4,3]
// remove(), remove(i) : 첫번째 삭제, i 위치 삭제
linkedList.remove(); // [4,3]
linkedList.remove(1); // [4]
// contains() : 데이터 여부 확인
linkedList.contains(4); // true
linkedList.contains(40);// false
// indexOf() : 데이터의 인덱스 찾기 (처음으로 나오는)
linkedList.indexOf(4); // 0
linkedList.indexOf(40); // -1
연결리스트의 내부 구조에 대해 살펴본다.
데이터 추가
head에 데이터를 추가할 때는, 추가한 노드가 기존 head를 가리키도록 하고 head를 바꿔준다.
tail(마지막)에 데이터를 추가할 때는, 마지막으로 이동해서 기존 마지막 노드가 새로운 노드를 가리키도록 하면 된다.
head, tail을 제외한 노드를 추가할 때는, 원하는 위치까지 이동 후 원래 있던 노드가 가리키는 노드를 새 노드가 가리키고 원래 있던 노드가 새 노드를 가리키도록 한다.
데이터 삭제
데이터를 삭제 시, 기존 노드를 따로 메모리에서 지우지 않아도 자바의 가비지 컬렉터에 의해 정리된다.
그래서 시작점인 head와 링크만 잘 연결해주면 된다.
head의 데이터를 삭제할 때는, 기존에 연결리스트가 가리키던 head를 head가 가리키는 노드로 바꿔주면 된다.
tail(마지막) 데이터를 삭제할 때는, tail의 이전 노드가 null을 가리키도록 바꿔주면 된다.
head, tail을 제외한 노드를 삭제할 때는, 삭제할 노드의 이전 노드를 삭제할 노드의 다음 노드를 가리키도록 바꿔주면 된다.