LinkedList 직접 구현해 보기
요약 정리
LinkedList(연결 리스트)를 구현하기 앞서 해당 자료 구조에 대해 알아보자.
우선 List라고 하면 인덱스 구조로 위치를 갖고, 순서를 보장하는 자료구조라고 설명할 수 있겠다.
더 나아가 LinkedList는 삽입 / 삭제의 장점을 갖지만, 특정 노드 탐색시 다른 List에 비해 오래 걸린다는 단점이 있다.
삽입 / 삭제의 장점을 갖을 수 있는 이유는 LinkedList의 종류에 따라 다르지만, 모두 노드의 연결로 이루어져 있으며 인접 노드의 주소를 포인터로 가르키고 있어 중간에 삽입 / 삭제가 이루어 져도 해당 노드를 끊고 인접 노드의 주소를 연결해 주면 될뿐 대표적인 ArrayList처럼 데이터를 미루거나 당기는 작업이 필요 없다.
LinkedList에는 Singly, Doubly, Circular 세가지 종류가 있다.
Singly LinkedList : 단방향 연결 리스트로 다음 노드의 주소를 가르키는 구조이다.
Doubly LinkedList : 양방향 연결 리스트로 이전/다음 노드의 주소를 가르키는 구조이다.
Circular LinkedList : 원형 연결 리스트로 추가적으로 처음, 마지막 노드가 주소를 가르키고 있는 구조이다.
구현
가장 기본형인 Singly LinkedList 의 메서드를 구현했다.
위에서 언급하였듯 다음 노드의 주소를 포인터로 가르키는 구조이기 때문에 next라는 필드로 다음 노드를 참조하도록 구성했다.
노드의 구성
- 현재 노드의 data를 저장할 data필드, 다음 노드를 참조할 next 필드를 정의하였다.
- 클래스 내부에서 사용할 데이터 타입을 외부에서 지정하기 위해 Generic을 사용하였다.
- Node 객체 비교가 필요할 경우를 대비하여 equals와 hashCode를 재정의하였다.
- 추후 LinkedList에서 StringBuilder를 통해 객체의 모든 요소를 출력하기 위해 toString을 재정의하였다.
public class Node<T> {
private T data;
private Node<T> next = null;
public Node(T data) {
this.data = data;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node<?> node = (Node<?>) o;
return Objects.equals(data, node.data) && Objects.equals(next, node.next);
}
@Override
public int hashCode() {
return Objects.hash(data, next);
}
@Override
public String toString() {
return data.toString();
}
}
가장 첫번째 노드를 저장할 Head 필드 구성
- static inner class로 노드를 사용 (Effective Java 3판 item24 참조)
-
- static을 생략하면 바깥 인스턴스로의 숨은 외부 참조를 갖게 된다.
- static을 생략하면 GC가 바깥 클래스의 인스턴스를 수거하지 못하는 메모리 누수가 생길 수 있다.
public class SimpleLinkedList<T> {
private Node<T> head = null;
private static class Node<T> {
...
}
}
SimpleLinkedList 구성
package Algorithms.자료구조.LinkedList;
import java.util.NoSuchElementException;
import java.util.Objects;
public class SimpleLinkedList<T> {
private Node<T> head = null;
private static class Node<T> {
private T data;
private Node<T> next = null;
public Node(T data) {
this.data = data;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node<?> node = (Node<?>) o;
return Objects.equals(data, node.data) && Objects.equals(next, node.next);
}
@Override
public int hashCode() {
return Objects.hash(data, next);
}
@Override
public String toString() {
return data.toString();
}
}
// Node 추가 메서드
public void add(T data) {
// 첫번째 일 경우
if(head == null) head = new Node<>(data);
else {
Node<T> node = this.head;
while (node.next != null) node = node.next;
// 마지막 노드를 탐색하여 인스턴스 생성
node.next = new Node<>(data);
}
}
// 노드 중간 삽입 메서드
public void add(int index, T data) {
if(index < 0) throw new IndexOutOfBoundsException("index can't smaller then 0");
// 0번쨰 index라면 head 변경과 동일
if(index == 0) {
addFirst(data);
return;
}
Node<T> temp = search(index);
Node<T> node = new Node<>(data);
node.next = temp.next;
temp.next = node;
}
// 노드삭제
public void remove(int index) {
if(this.head == null) {
if(0 < index) throw new IndexOutOfBoundsException("Index bigger then size");
throw new NoSuchElementException("First Node is Empty");
}
// 첫번째 요소라면 헤드를 변경
if(index == 0) {
head = head.next;
return;
}
int n = 1;
Node<T> node = this.head;
while (n < index) {
if(node == null) {
throw new IndexOutOfBoundsException("index bigger then size");
}
node = node.next;
n++;
}
node.next = node.next == null ? null : node.next.next;
}
public void addFirst(T data) {
if(this.head == null) throw new IndexOutOfBoundsException("index bigger then size");
Node<T> node = new Node<>(data);
node.next = this.head;
this.head = node;
}
public void addLast(T data) {
add(data);
}
public Integer indexOf(T data) {
if(this.head == null) return null;
int n = 0;
Node<T> node = this.head;
while (node != null) {
// 노드의 요소와 찾는 요소가 같다면 return
if (node.data == data) return n;
node = node.next;
n++;
}
return null;
}
// 노드 순회
private Node<T> search(int index) {
if(this.head == null) throw new IndexOutOfBoundsException("index bigger then size");
int n = 1;
Node<T> node = this.head;
while (n < index) {
node = node.next;
if (node == null) throw new IndexOutOfBoundsException("index bigger then size");
n++;
}
return node;
}
@Override
public String toString() {
/*
배열의 형식 구성
ex) [1, 2, 3, ... , n]
*/
StringBuilder stringBuilder = new StringBuilder("[");
Node<T> node = this.head;
stringBuilder.append(node);
while (node.next != null) {
//모든 노드 탐색
node = node.next;
stringBuilder.append(", ").append(node);
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}
Main 메서드를 이용한 메서드 테스트
package Algorithms.자료구조.LinkedList;
public class Main {
public static void main(String[] args) {
SimpleLinkedList<Integer> simpleLinkedList = new SimpleLinkedList<>();
simpleLinkedList.add(4);
simpleLinkedList.add(0,2);
simpleLinkedList.add(1,3);
simpleLinkedList.add(0,3);
System.out.println(simpleLinkedList);
simpleLinkedList.addFirst(1);
simpleLinkedList.addLast(5);
System.out.println(simpleLinkedList);
simpleLinkedList.remove(simpleLinkedList.indexOf(3));
System.out.println(simpleLinkedList);
}
}
간단한 동작 구현이라 예외 처리가 부족한 부분이 있을 수 있습니다. 긴 글 읽어 주셔서 감사합니다 :)