## 20. LinkedList 자료구조 구현하기
- 목록 관리 범용 클래스 LinkedList 정의
- LinkedList 구동원리 이해 및 구현
- 중첩 클래스 활용
- MemberHandler와 BoardHandler에 적용
LinkedList 자료구조 구현하기
목록 관리 범용 클래스 LinkedList 정의
LinkedList 구동원리 이해 및 구현
ㄴ handler 패키지에 존재하는 ArrayList.java 소스파일을 util 로 이동시킴
=> eclipse는 파일을 다른 패키지로 이동 시 해당 파일에 대한 패키지 선언도 자동으로 변경됨 (이클립스 Refactoring 기능 중 하나)
ㄴ 소스 파일을 이동할 때 관련된 패키지 선언을 자동으로 업데이트하여 일관성을 유지하고 컴파일 에러를 방지
ㄴ util 패키지에 Node 클래스 생성
Node.java
ㄴ util 패키지에 LinkedList 클래스 생성
LinkedList.java
=>
ㄴ Node 클래스는 연결 리스트의 노드를 나타냄
ㄴ 각 노드는 value라는 데이터와 next라는 참조 변수를 가지고 있음
ㄴ value 변수는 노드에 저장되는 데이터를 나타내고, next 변수는 다음 노드를 가리키는 역할을 함
ㄴ LinkedList 클래스는 실제로 연결 리스트를 구현하는 클래스
ㄴ LinkedList 클래스는 tail이라는 변수를 가지고 있는데, 이 변수는 현재 리스트의 마지막 노드를 가리키는 역할을 함
ㄴ add 메서드는 새로운 값을 리스트에 추가하는 역할을 함
ㄴ 새로운 노드를 생성
ㄴ 새로운 노드의 value 변수에 전달받은 값을 저장
ㄴ 리스트의 마지막 노드에 새로운 노드를 연결함
=> tail 변수가 null인 경우에는 리스트가 비어있으므로 tail에 새로운 노드(주소값)를 할당
=> tail 변수가 null이 아닌 경우에는 이전의 마지막 노드의 next 변수에 새로운 노드를 할당하여 연결(주소값 할당)하고, tail 변수를 새로운 노드로 업데이트함
=> 이렇게 하면 리스트에 새로운 노드가 추가되고, tail 변수는 항상 리스트의 마지막 노드를 가리키게 됨
BoardHandler 에 적용
BoardHandler.java
ㄴ ArrayList => LinkedList 로 변경해주고 bitcamp.util.LinkedList 를 import 해줌
LinkedList.java
ㄴ 증가 값을 담을 size 라는 변수 생성
LinkedList.java
ㄴ size 를 이용해 해당 번째의 노드를 받아올 수 있음
LinkedList.java
ㄴ 노드가 하나 만들어질 때마다 size 를 증가 시킴
LinkedList.java
ㄴ head 라는 변수는 현재 리스트의 첫 번째 노드를 가리키는 역할
LinkedList.java
ㄴ head가 null인 경우 연결 리스트의 첫 번째 노드인 head에 새로운 노드를 연결
=> 리스트가 비어있는 경우에만 첫 번째 노드로 새로운 노드를 지정하기 위한 조건
if 문 두 개를 합치기
LinkedList.java
=>
LinkedList.java
ㄴ 연결리스트가 비어있다면(head가 null인 경우) head 에 새로운 노드를 지정하여 새로운 노드를 첫 번째 노드로 설정
=> 이때 head 변수에 새로운 노드의 주소를 할당
ㄴ 연결 리스트가 비어있지 않다면 (head가 null이 아닌 경우), 이전의 마지막 노드인 tail의 next 변수에 새로운 노드를 연결함
=> 이를 통해 새로운 노드가 리스트의 마지막에 추가되는 연결이 이루어짐
LinkedList.java
ㄴ Object 타입의 배열 arr를 생성
ㄴ 배열의 크기는 연결 리스트의 크기인 this.size로 설정
ㄴ 현재 노드를 가리키는 node 변수를 head로 초기화 (head는 연결 리스트의 첫 번째 노드를 가리킴)
ㄴ 반복문을 사용하여 모든 노드를 순회 => 반복문의 조건은 i가 this.size보다 작을 때
ㄴ arr[i] 에 value 값을 하나씩 넣으면서 node를 다음 노드로 이동시켜감 => 이를 통해 arr[i] 에 value 를 하나씩 넣으면서 연결 리스트의 다음 요소로 이동
ㄴ 반복문이 종료된 후에는 모든 요소를 순회한 상태이므로, 배열 arr에 연결 리스트의 모든 요소가 저장되어 있음 => 배열 arr을 반환
BoardHandler 에 적용
BoardHandler.java
ㄴ list() -> getList() 로 변경 => LinkedList 클래스에 정의되어있는 메서드 이용
LinkedList.java
ㄴ getList() 의 node 도 cursor 라는 이름으로 레퍼런스 이름을 변경해줌 => 가리키는 위치를 의미하므로
ㄴ retrieve(Object value)
ㄴ 현재 노드를 가리키는 cursor 변수를 head로 초기화하여 리스트의 첫 번째 노드부터 순회 시작
ㄴ cursor 가 null 이 아닐 때 까지 반복 => 리스트의 끝까지 순회하는 역할
ㄴ 각 노드에서 현재 값 cursor.value 와 주어진 값 value 를 비교
ㄴ cursor가 null이 아닐 때까지 반복하여 연결 리스트의 모든 요소를 순회하며 현재 노드의 value와 주어진 값 value를 비교
ㄴ 값이 일치하면 해당 값을 반환하고 메서드를 종료
ㄴ 값이 일치하지 않으면 다음 노드로 이동하기 위해 cursor 를 다음노드로 설정 => cursor = cursor.next
ㄴ 반복문이 종료되면 주어진 값과 일치하는 요소가 없으므로 null을 반환
BoardHandler.java
ㄴ get -> retrieve 로 변경 => LinkedList 클래스에 정의되어있는 메서드 이용
LinkedList.java
=>
LinkedList.java
=>
LinkedList.java
ㄴ 삭제 후 다음 노드의 주소를 이전 노드로 당겨와야 하기 때문에 저장해 둘 필요가 있음
LinkedList.java
LinkedList.java
ㄴ prev 변수는 현재 노드의 이전 노드를 가리키는 역할을 함 => 삭제할 요소의 이전 노드를 추적하기 위해 추가
ㄴ 현재 커서를 다음 노드로 이동시켜가면서 cursor가 null이 아닐 때까지 반복하여 연결 리스트의 모든 요소를 순회하며 현재 노드의 value와 주어진 값 value를 비교
LinkedList.java
ㄴ 가비지 객체를 초기화 시켜서 가비직 인스턴스를 가리키지 않도록 cursor.next 와 cursor.value 의 값을 모두 null 로 초기화 시킴
LinkedList.java
ㄴ 값을 한 개 삭제하는 것이므로 size 값을 하나 줄여줌
LinkedList.java
ㄴ 삭제할 노드가 끝 노드라면 tail(마지막 노드)은 이전 노드인 prev 가 되고, size 줄이는 코드를 가비치 객체 초기화보다 먼저 실행
LinkedList.java
ㄴ 삭제할 노드가 시작 노드라면 head(시작 노드)는 다음 노드를 가리키는 cursor.next 가 됨
LinkedList.java
ㄴ 삭제할 노드가 시작 노드인 경우 (prev == null)
ㄴ head = cursor.next; 코드를 통해 시작 노드를 삭제하고, 새로운 시작노드를 head 로 지정
ㄴ 만약, 삭제된 노드가 연결리스트의 마지막 노드였다면, head 와 tail 을 모두 null 로 설정하여 빈 연결 리스트가 되도록 함
=> head와 tail을 모두 null로 설정하여 리스트를 초기화
LinkedList.java
ㄴ prev.next == null 코드는 cursor.next == null 이라고도 표현 가능함
=> 삭제할 노드가 끝 노드인지 확인
LinkedList.java
ㄴ 삭제가 완료되면 true 값을 리턴
LinkedList.java
ㄴ 이전 노드에 다음 노드의 주소를 저장하는 것은 삭제할 노드가 시작 노드가 아니어야 하므로 일단 주석으로 막기
LinkedList.java
LinkedList.java
ㄴ if else ~ if else 로 묶어주기
ㄴ 삭제할 노드가 시작 노드도 아니고 끝 노드도 아닌 중간에 있는 노드라면 다음 노드의 주소를 이전 노드에 저장
LinkedList.java
ㄴ cursor == head => prev == null
=> 시작 노드인 경우 prev 변수가 null 이므로 시작노드인 경우의 조건을 따질 때 prev 가 null 인지를 확인함
(cursor가 주어진 값과 일치하는 경우, prev가 null인지 확인하여 첫 번째 노드인지 여부를 판단)
=>
LinkedList.java
ㄴ remove(Object value) 메서드
public boolean remove(Object value) {
Node prev = null;
Node cursor = this.head;
while (cursor != null) {
if (cursor.value.equals(value)) {
// 삭제할 노드가 시작 노드라면
if (prev == null) {
head = cursor.next;
// 삭제할 노드가 끝 노드라면
if (head == null) {
tail = null;
}
} else if (cursor.next == null) { // 삭제할 노드가 끝 노드라면
tail = prev;
tail.next = null;
} else {
// 다음 노드의 주소를 이전 노드에 저장한다.
prev.next = cursor.next;
}
size--;
// 가비지 객체를 초기화시켜서 가비지가 인스턴스를 가리키지 않도록 한다.
cursor.next = null;
cursor.value = null;
return true;
}
// 현재 cursor가 가리키는 노드를 prev에 보관한다.
prev = cursor;
// 현재 커서를 다음 노드로 이동한다.
cursor = cursor.next;
}
return false;
}
1. prev == null
ㄴ 삭제할 노드가 시작 노드인 경우
=> prev가 null이므로 head를 삭제할 노드의 다음 노드인 cursor.next로 업데이트 함
=> 만약 head가 null이 되어 빈 리스트가 되었다면, tail도 null로 설정하여 리스트가 비어있음을 표시
2. cursor.next == null:
ㄴ 삭제할 노드가 끝 노드인 경우
=> tail을 이전 노드인 prev로 업데이트 함
3. 그 외:
ㄴ 삭제할 노드가 시작 노드나 끝 노드가 아닌 경우
=> 다음 노드의 주소를 이전 노드인 prev의 next에 저장하여 삭제할 노드를 리스트에서 분리
=> 코드는 삭제할 노드를 찾고 삭제 후 리스트를 정리하는 작업을 수행하며,
삭제가 성공적으로 이루어지면 true를 반환하고 그렇지 않으면 false를 반환
=> 또한, 삭제한 노드의 가비지 객체를 초기화하여 메모리 누수를 방지
=> 이렇게 변경된 코드를 사용하면 주어진 값과 일치하는 노드가 리스트에서 삭제되고,
리스트의 구조와 정합성이 유지됨
BoardHandler 에 적용
BoardHandler.java
ㄴ delete -> remove 로 변경 => LinkedList 클래스에 정의되어있는 메서드 이용
잘 구현했는지 LinkedList 클래스 안에서 테스트 하는 방법
add(Object value);
LinkedList.java
retrieve(Object value);
LinkedList.java
remove(Object value);
LinkedList.java
LinkedList.java
LinkedList.java
LinkedList.java
LinkedList.java
LinkedList.java
LinkedList.java
LinkedList.java
ㄴ 100 ~ 500 까지는 삭제가 잘 되어 true 가 리턴 되고, add 에서 추가하지 않았던 600 을 넣으면 false 가 리턴 됨
LinkedList.java
ㄴ 모두 삭제 후 add(Object value) 매서드까지 잘 실행되는지 확인
목록 관리 범용 클래스 LinkedList 정의
중첩 클래스 활용
Node.java
ㄴ Node.java 에 있는 코드 복사
LinkedList.java
ㄴ Node.java 에 있는 코드를 LinkedList 클래스 안에 넣어 중첩 클래스로 활용
LinkedList.java
ㄴ LinkedList 클래스 내부에 정의된 내부 클래스(static nested class)로 선언되었기 때문에 static 키워드를 사용하여 정적(static) 멤버로 선언
ㄴ 이제 Node.java 의 코드는 모두 LinkedList 에 중첩 클래스로 활용되었으므로 Node.java 파일은 삭제해도 됨
