자바에서의 Linked List 기본 구현 #1
Description
자바는 C와 다르게 직접적인 포인터 사용이 불가능 합니다.
따라서 클래스의 instance 변수 타입을 자기자신으로 지정 함 으로써
재귀적으로 Linked List를 구현합니다.
만약 ListNode 라는 클래스가 있다면
초기의 코드는 다음과 비슷할 것 입니다.
class ListNode {
int item;
ListNode next;
public ListNode(int item) {
this.item = item;
this.next = null;
}
}
인스턴스 변수 next를 자기 자신의 타입을 다시 정의함으로써
연결리스트를 구현합니다.
ListNode listNode = new ListNode();
listNode->next = new ListNode();
이런 경우에 리스트의 구조는
다음과 같습니다.
listNode -> listNode
이걸 일반화 시킨 add 연산은 어떻게 일어나게 될 까요??
크게 2가지 방법이 존재합니다.
- 재귀
public static void add(ListNode listNode, int value) {
if (listNode.next != null) {
add(listNode.next, value);
} else {
listNode.next = new ListNode(value);
}
}
- 반복문
public static void add(ListNode listNode, int value) {
while (listNode.next != null) {
listNode = listNode.next;
}
listNode.next = new ListNode(value);
}
두 방법모두 기본적인 아이디어는 동일합니다
listNode 의 next가 null인 경우 next에 추가해주는 것이죠
그런데 지금의 ListNode 클래스는 좋아보이지 않습니다.
누구나 instance variable에 접근 가능하기 떄문인데요
이는 클래스를 사용함에있어 큰 장애를 일으킬 수도 있습니다.
따라서 클래스를 조금 수정해보도록 하겠습니다.
class ListNode {
private int item;
private ListNode next;
public ListNode(int item) {
this.item = item;
this.next = null;
}
public int getItem() {
return item;
}
public ListNode getNext() {
return this.next;
}
public void setNext(ListNode listNode) {
this.next = listNode;
}
}
이제 우리는 ListNode의 instance variable을 보호하면서 사용할 수 있습니다.
이제 더 이상 ListNode.next 를 통해서 next를 초기화 하는 것이 아니라
listNode.setNext(new ListNode(item))다음과 같은 식으로 변경 됐습니다.
만약 List에 추가할 원소가 정해져 있다면 어떨까요??
모든 원소 추가를 한번에 하는 메서드도 추가해 보겠습니다.
public static ListNode addAllNode(int... num) {
ListNode head = null;
ListNode start = null;
for (int i = 0; i < num.length; i++) {
if (head == null) {
head = new ListNode(num[i]);
start = head;
continue;
}
while (head.getNext() != null) {
head = head.getNext();
}
head.setNext(new ListNode(num[i]));
}
return start;
}
이 방식을 이용하면 한번에 add 작업을 완료할 수 있습니다.
만약 이 ListNode에 특정한 index의 요소를 반환하는 get메서드를 만들고 싶다면 어떻게 만들면 될까요??
반복문을 쓰면 쉽게 해결 가능합니다.
public static ListNode getNodeByIndex(ListNode listNode, int index) {
if (index < 0) {
throw new IllegalArgumentException("0보다 작은 index는 올 수 없습니다.");
}
for (int i = 0; i < index; i++) {
listNode = listNode.getNext();
}
return new ListNode(listNode.getItem());
}
이러한 테크닉을 이용하면 ListNode를 반전시키는 reverseListNode 또한 만들어 낼 수 있습니다.
컨셉은 다음과 같습니다.
ListNode의 next가 null이되는 시점부터 시작 -> reverseListNode에 추가 -> next가 null이되는 이전시점의 ListNode방문
-> reverseListNode에 추가 .... 반복
구현을 쉽게 하기위해 ListNode의 size를 측정하는 getListSize 메서드를 추가하겠습니다.
public int getListSize() {
int count = 0;
ListNode listNode = this;
while (listNode != null) {
count++;
listNode = listNode.getNext();
}
return count;
}
ListNode의 next가 존재할 때마다 count는 증가하며
이는 곧 해당 List의 크기가 됩니다.
이제 전체 크기를 알았으니 reverseListNode를 쉽게 만들 수 있습니다.
반전된 List를 만드는 로직은 다음과 같습니다.
public static ListNode reverseListNode(ListNode listNode) {
ListNode answer = null;
int index = listNode.getListSize();
for (int i = index; i > 0; i--) {
if (answer == null) {
answer = getNodeByIndex(listNode, i);
continue;
}
addNode(answer, getNodeByIndex(listNode, i));
}
return answer;
}
getNodeByIndex를 이용한다면 ListNode의 특정 원소를 계속해서 더 해줄수 있습니다.
따라서 다양한 방식으로 기존의 만들어 놓은 ListNode를 활용 가능해집니다.
또한 , 단순히 reverseListNode를 만드는 목적이라면
재귀함수를 쓰는 방법이 더 좋아보입니다.
이는 따로 구현해 보시면 좋을 것 같습니다.
마지막으로 만들어진 ListNode를 출력하는 print함수를 만들어 보겠습니다.
public static void printListNode(ListNode listNode) {
while (listNode != null) {
logger.info("{}", listNode.getItem());
listNode = listNode.getNext();
}
}
이렇게 기초적인 add, addAll , get , reverse , print 를 구현해 봤습니다.
관련된 내용을 따로 정리하여 remove등의 메서드도 만들어 보시면 좋을 것 같습니다.