연결리스트 개념 알아보기
1. 연결리스트란 (Linked List)?
- 데이터를 링크로 연결해서 관리하는 자료구조
- 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지 않음
2. 연결 리스트의 장점
- 데이터 공간을 미리 할당할 필요 없다
- 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이
3. 연결 리스트의 단점
- 연결 구조를 위한 별도 데이터 공간 필요
- 연결 정보를 찾는 시간이 필요 (접근 속도가 상대적으로 느림)
- 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요
4. 연결 리스트의 기본 구조
- 노드(Node)
- 데이터 저장 단위로, 값과 포인터로 구성
단방향 리스트를 기준으로 데이터를 추가하는 예시를 살펴보자
- 가장 앞에 데이터 추가
1. 추가할 데이터를 담을 노드 생성
2. 링크 연결 작업
3. head 이전 작업
- 가장 뒤에 데이터 추가
1. 추가할 데이터를 담을 노드 생성
2. head로 부터 끝 노드까지 순회
3. 링크 연결 작업
- 중간에 데이터 추가
1. 추가할 데이터를 담을 노드 생성
2. head로 부터 데이터를 추가 위치 직전 노드까지 순회
3. 링크 연결 작업
* 주의할점 : 중간에 링크가 끊기지 않도록 연결 작업 필요.
- new_node.next 에 data1.next 로 연결
- data1.next에 new_node 연결
단방향 리스트를 기준으로 데이터를 삭제하는 예시를 살펴보자
* Java의 경우 GC(Garbage Collection) 기능이 존재하여 메모리를 알아서 회수한다.
그러므로 null 처리 또는 링크를 끊어주면 된다.
- 가장 앞에 데이터 삭제
1. 삭제 대상 노드 지정(delete_node)
2. head 이전 작업
3. delete_node 삭제
- 가장 뒤에 데이터 삭제
1. head로 부터 가장 끝까지 순회
2. 끝 노드 삭제
3. 삭제 이전 노드의 링크 처리
- 중간에 데이터 삭제
1. head로부터 삭제 대상 노드까지 순회 및 해당 노드 지정(delete_node)
2. 삭제 대상 이전/이후 노드의 링크 연결 작업
3. delete_node 삭제
연결리스트 경우 LinkedList가 연결리스트를 구현한 클래스이다. 그렇기 때문에 추가 삭제 를 쉽게 구현이 가능하다.
|
// 노드
import java.util.LinkedList;
class Node {
}
public class Main {
public static void main(String[] args) {
LinkedList<Node> list = new LinkedList<>();
} |
- 노드 클래스를 생성한 후 제너릭 변수로 선언해서 사용하면 된다.