연결 리스트
연결 리스트는 내부에 노드 와 헤더를 갖는다.
노드는 데이터를 갖고 다음 노드의 주소값을 알고있다.
자바로 단방향 연결 리스트 구현
자바로 단방향 연결 리스트를 구현해보았다. 자료구조의 개념을 익히기 위함이라 완벽한 구현은 아닐수도 있다.
간단하게 내부 클래스로 Node 를 만들고 연결 리스트의 추가, 삭제, 조회 메서드를 구현했다.
첫 생성 시엔 다음 노드의 주소값의 초기값을 null 로 줘서 다음 주소값을 모르도록 설정했다.
연결 리스트를 생성하는 시점에 첫 노드로서 헤더를 만들고 생성, 삭제, 조회 시 헤더가 이 메서드들의 반복문의 시작점이 된다.
조회 시 헤더를 조회 할 필요는 없으므로 헤더의 다음 노드부터 조회한다.
public class LinkedList {
Nodes header;
public LinkedList() {
header = new Node();
}
// 추가
void append(int d) {
Node end = new Node(d);
Node n = header;
while (n.next != null) {
n = n.next;
}
n.next = end;
}
// 삭제
void delete(int data) {
Node n = header;
while (n.next != null) {
if (n.next.data == data) {
n.next = n.next.next;
} else {
n = n.next;
}
}
}
// 조회
void retrieve() {
Node n = header.next;
while (n.next != null) {
System.out.print(n.data + " -> ");
n = n.next;
}
System.out.println(n.data);
}
public static class Node {
int data;
Node next = null;
public Node() {
}
public Node(int data) {
this.data = data;
}
}
}ㄴ append()
데이터 값을 매개변수로 받아 그 데이터로 마지막 노드를 만들고
처음부터 반복문을 돌아서 이전 마지막 노드를 찾아 그 노드에 새로 만든 마지막 노드의 주소값을 할당한다.
ㄴ delete()
데이터 값을 매개변수로 받아 반복문을 돌아 그 데이터에 해당하는 목표 노드를 찾는다.
a -> b -> c 순서의 노드 중 b 가 목표 노드라면 a 노드 에는 c 노드 주소를 할당한다.
ㄴ retrieve()
조회 시에는 header 의 데이터값을 조회 할 필요는 없으므로 header 의 다음 노드부터 시작해서
다음 노드 주소가 null 인 노드(마지막 노드) 까지 값을 출력한다.
LinkedList 클래스에 아래처럼 메인 메서드를 작성하면 제대로 동작함을 알 수 있다.
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);
linkedList.retrieve();
linkedList.delete(1);
linkedList.delete(4);
linkedList.retrieve();
}
'알고리즘 > 자료구조' 카테고리의 다른 글
| [자료구조] LinkedList (0) | 2023.10.02 |
|---|
