1. LinkedList 직접 구현하여 사용하기
LinkedList는 ArrayList와 달리 배열이 아닌 상호 연결된 Node를 사용하여 구현할 수 있다. 이전 포스팅에서 설명하였듯이 Node가 데이터값과 다른 Node에 대한 주소값을 갖고 있어 해당 주소값을 기반으로 저장된 값을 참조할 수 있게 된다.
LinkedList에 대한 더 자세한 설명은 아래의 링크를 통해 이전의 포스팅을 참조하자.
https://hongjw1938.tistory.com/4?category=884192
자료구조(Java) - Collection Framework
자바(Java)에서는 다양한 자료구조를 사용자가 쉽게 활용하도록 성능적으로도 우수하며 코딩에 할애하는 시간을 줄일 수 있는 Collection Framework를 제공하고 있다. 이 Collection Framework는 자료를 저장
hongjw1938.tistory.com
다음의 코드를 통해 직접 구현할 수 있는 방법에 대해 확인해보자.
package list;
import java.util.NoSuchElementException;
public class LinkedListImpl<T> {
private int size;
private Node<T> head;
private Node<T> tail;
// Head 부분에 노드 추가하기
public boolean addFirst(T data){
Node<T> node = new Node<>(data);
node.next = this.head;
node.previous = this.tail;
// 기존에 아무것도 없었다면
if(this.size == 0){
this.tail = node;
// 기존에 Node가 하나라도 있었다면
} else {
this.head.previous = node;
this.tail.next = node;
}
this.head = node;
this.size++;
return true;
}
// Tail 부분에 노드 추가하기
public boolean addLast(T data){
Node<T> node = new Node<>(data);
node.previous = this.tail;
node.next = this.head;
// 기존에 Node가 없었다면
if(this.size == 0){
this.head = node;
// 기존에 Node가 하나라도 있었다면
} else {
this.head.previous = node;
this.tail.next = node;
}
this.tail = node;
this.size++;
return true;
}
// 중간에 노드 추가하기
// idx는 0번부터 시작한다고 가정
public boolean add(T data, int idx){
if(idx == 0){
addFirst(data);
} else if(idx >= this.size){
addLast(data);
} else {
Node<T> newNode = new Node<>(data);
Node<T> current = this.head;
for(int i=0; i < idx; i++){
current = current.next;
}
newNode.next = current.next;
current.next.previous = newNode;
current.next = newNode;
newNode.previous = current;
this.size++;
}
return true;
}
// Head Node 빼서 반환하기
// Head를 바꿔주고 기존 tail과 바뀐 head가 서로 가리키도록 변경
public Node<T> pollFirst(){
// 기존에 Node가 없었다면
if(this.size == 0){
throw new NoSuchElementException();
}
Node<T> retNode = this.head;
// 현재 1개밖에 없다면 모두 null로 만들고 반환
if(this.size == 1){
this.head = null;
this.tail = null;
this.size--;
return retNode;
}
this.head = retNode.next;
this.head.previous = this.tail;
this.tail.next = this.head;
this.size--;
return retNode;
}
// Tail Node 빼서 반환하기
// Tail을 바꿔주고 기존 Head와 바뀐 Tail이 서로 가리키도록 변경
public Node<T> pollLast(){
// 기존에 Node가 없었다면
if(this.size == 0){
throw new NoSuchElementException();
}
Node<T> retNode = this.tail;
// 현재 1개밖에 없다면 모두 null로 만들고 반환
if(this.size == 1){
this.head = null;
this.tail = null;
this.size--;
return retNode;
}
this.tail = retNode.previous;
this.head.previous = this.tail;
this.tail.next = this.head;
this.size--;
return retNode;
}
// 중간 Node 빼서 반환하기
public Node<T> poll(int idx){
if(idx == 0){
return pollFirst();
} else if(idx >= this.size-1){
return pollLast();
} else {
Node<T> target = head;
for(int i=0; i < idx; i++){
target = target.next;
}
target.previous.next = target.next;
target.next.previous = target.previous;
return target;
}
}
// 현재 Node의 개수
public int size(){
return this.size;
}
// 현재 비어있는지 확인인
public boolean isEmpty(){
return this.size == 0;
}
// Head값만 참조해보기
public Node<T> peek(){
return this.head;
}
// Iterator 반환하기
public Iterator getIterator(){
return new Iterator();
}
public static class Node<T>{
private T data;
private Node<T> next;
private Node<T> previous;
public Node(T data){
this.data = data;
}
public void setData(T data){
this.data = data;
}
public T getData(){
return this.data;
}
public Node<T> getNext() {
return this.next;
}
public Node<T> getPrevious(){
return this.previous;
}
}
class Iterator{
// 현재 탐색할 순서를 가리키는 Index
private int nextIndex;
private int prevIndex;
private Node<T> next;
private Node<T> previous;
private Node<T> lastReturned;
public Iterator(){
next = head;
previous = null;
nextIndex = 0;
prevIndex = -1;
}
// next 값이 있는지 확인하는 메소드
public boolean hasNext(){
return this.nextIndex < size();
}
// next 값을 반환하는 메소드
public Node<T> next(){
if(!hasNext()){
throw new NoSuchElementException();
}
if(nextIndex >= 1){
prevIndex = nextIndex - 1;
previous = lastReturned;
}
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned;
}
// previous 값이 있는 확인하는 메소드
public boolean hasPrevious(){
return prevIndex >= 0;
}
// previous 값을 반환하는 메소드
public Node<T> previous(){
if(!hasPrevious()){
throw new NoSuchElementException();
}
lastReturned = previous;
previous = previous.previous;
next = lastReturned.next;
nextIndex--;
prevIndex--;
return lastReturned;
}
}
}
각각의 Method에 대해 간단히 확인해보자.
① Node Inner Class
Node Inner Class는 각각의 데이터를 연결하여 Node에 캡슐화한 뒤 상호 연결된 Node 간에 주소값을 저장하여 서로 참조할 수 있도록 구현하기 위해 사용한다. 아래의 표를 확인해보자.
| Field | 내용 |
| data | Generic 기반의 데이터를 의미한다. |
| next | 다음 노드의 주소값을 가지고 있다. |
| previous | 이전 노드의 주소값을 가지고 있다. |
위 내용을 참조하여 아래 코드를 통해 다시 한 번 보도록 하자.
public static class Node<T>{
private T data;
private Node<T> next;
private Node<T> previous;
public Node(T data){
this.data = data; // 생성자를 통해 Generic Data 값을 저장한다.
}
public void setData(T data){
this.data = data;
}
public T getData(){
return this.data;
}
public Node<T> getNext() {
return this.next;
}
public Node<T> getPrevious(){
return this.previous;
}
}Set을 통해 Next / Previous를 저장하는 코드가 없어 헷갈릴 수 있는데 Inner Class라서 LinkedList Class에서 직접 next / previous에 저장하는 방식으로 코드를 짰다. 위 코드를 통해 data를 저장하고 각 Node가 갖고 있는 next / previous 주소값을 통해 상호 Node를 참조할 수 있다는 것을 확인할 수 있다.
② Add Method
Add는 연결리스트에서 특정 Node의 앞 뒤 혹은 전체 연결리스트의 머리 / 꼬리 부분에 Node를 추가하는 method들이다. 아래 코드를 다시 보자.
public class LinkedListImpl<T> {
private int size;
private Node<T> head;
private Node<T> tail;
// Head 부분에 노드 추가하기
public boolean addFirst(T data){
Node<T> node = new Node<>(data);
node.next = this.head;
node.previous = this.tail;
// 기존에 아무것도 없었다면
if(this.size == 0){
this.tail = node;
// 기존에 Node가 하나라도 있었다면
} else {
this.head.previous = node;
this.tail.next = node;
}
this.head = node;
this.size++;
return true;
}
// Tail 부분에 노드 추가하기
public boolean addLast(T data){
Node<T> node = new Node<>(data);
node.previous = this.tail;
node.next = this.head;
// 기존에 Node가 없었다면
if(this.size == 0){
this.head = node;
// 기존에 Node가 하나라도 있었다면
} else {
this.head.previous = node;
this.tail.next = node;
}
this.tail = node;
this.size++;
return true;
}
// 중간에 노드 추가하기
// idx는 0번부터 시작한다고 가정
public boolean add(T data, int idx){
if(idx == 0){
addFirst(data);
} else if(idx >= this.size){
addLast(data);
} else {
Node<T> newNode = new Node<>(data);
Node<T> current = this.head;
for(int i=0; i < idx; i++){
current = current.next;
}
newNode.next = current.next;
current.next.previous = newNode;
current.next = newNode;
newNode.previous = current;
this.size++;
}
return true;
}
}제일 상단에 head / tail이 Inner Class인 Node의 객체임을 확인할 수 있다. 사실 위 코드에서는 양방향 환형 연결리스트를 구현한다고 생각하여 짠 코드이므로 head는 tail만 알고 있으면 tail의 next로 구해서 가져올 수는 있다. 어쨋건 head와 tail을 통해 제일 첫 / 마지막 노드에 빠르게 접근할 수 있도록 구현할 수 있다.
addFirst method에서는 head부분에 Node를 추가하므로 기존에 아무것도 없었다면 해당 추가되는 Node가 head이자 tail이 되며, 기존에 1개라도 Node가 있었다면 해당 Node와 연결해주면 코드를 완성할 수 있다. 기존 head를 밀어내고 해당 Node의 이전 Node를 추가되는 Node로 지정하고 기존 tail Node의 next를 현재 Node로 지정해주면 된다.
addLast method에서는 tail 부분에 Node를 추가하는 코드인데, 동일한 Logic으로 기존 head / tail 노드의 상호 참조 값을 변경해주는 방식으로 구현할 수 있다.
add method는 중간의 특정 index에 Node를 추가하는 방식이다. 이 또한 해당 Node를 추가하는 위치의 양 옆 Node의 참조값을 변경해주는 코드를 작성하면 된다.
③ Poll method
이는 Add와 반대로 연결리스트의 특정 위치에 있는 Node를 제거하는 방법이다. Logic은 Add와 유사하다. 단지 제거 후 양 옆 노드의 참조값을 변경해주는 것 뿐이다. 아래 코드를 통해 다시 한 번 확인해보자.
public class LinkedListImpl<T> {
private int size;
private Node<T> head;
private Node<T> tail;
// Head Node 빼서 반환하기
// Head를 바꿔주고 기존 tail과 바뀐 head가 서로 가리키도록 변경
public Node<T> pollFirst(){
// 기존에 Node가 없었다면
if(this.size == 0){
throw new NoSuchElementException();
}
Node<T> retNode = this.head;
this.head = retNode.next;
this.head.previous = this.tail;
this.tail.next = this.head;
this.size--;
return retNode;
}
// Tail Node 빼서 반환하기
// Tail을 바꿔주고 기존 Head와 바뀐 Tail이 서로 가리키도록 변경
public Node<T> pollLast(){
// 기존에 Node가 없었다면
if(this.size == 0){
throw new NoSuchElementException();
}
Node<T> retNode = this.tail;
this.tail = retNode.previous;
this.head.previous = this.tail;
this.tail.next = this.head;
this.size--;
return retNode;
}
// 중간 Node 빼서 반환하기
public Node<T> poll(int idx){
if(idx == 0){
return pollFirst();
} else if(idx >= this.size-1){
return pollLast();
} else {
Node<T> target = head;
for(int i=0; i < idx; i++){
target = target.next;
}
target.previous.next = target.next;
target.next.previous = target.previous;
return target;
}
}pollFirst method부터 확인해보면 현재 Node가 없다면 예외를 발생시키고 있다면 기존의 head를 빼고 해당 head의 next를 head로 변경하여 참조값을 바꾸어주는 역할을 수행하는 것을 알 수 있다.
pollLast method는 tail을 빼고 tail의 이전(previous) Node를 tail로 바꾸고 참조값을 바꾸어 준다.
poll method는 중간의 특정 index 값의 node를 빼내는 방식이다. 코드를 통해 쉽게 이해할 수 있다.
④ Iterator Inner Class
이 Class는 Inner Class로 구현하여 연결리스트의 head부터 시작하여 next로 순환하면서 저장된 값을 불러올 수 있고 또한 previous 방향으로도 순회할 수 있도록 구현되었다. 아래 코드를 보자.
class Iterator{
// 현재 탐색할 순서를 가리키는 Index
private int nextIndex;
private int prevIndex;
private Node<T> next;
private Node<T> previous;
private Node<T> lastReturned;
public Iterator(){
next = head;
previous = null;
nextIndex = 0;
prevIndex = -1;
}
// next 값이 있는지 확인하는 메소드
public boolean hasNext(){
return this.nextIndex < size();
}
// next 값을 반환하는 메소드
public Node<T> next(){
if(!hasNext()){
throw new NoSuchElementException();
}
if(nextIndex >= 1){
prevIndex = nextIndex - 1;
previous = lastReturned;
}
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned;
}
// previous 값이 있는 확인하는 메소드
public boolean hasPrevious(){
return prevIndex >= 0;
}
// previous 값을 반환하는 메소드
public Node<T> previous(){
if(!hasPrevious()){
throw new NoSuchElementException();
}
lastReturned = previous;
previous = previous.previous;
next = lastReturned.next;
nextIndex--;
prevIndex--;
return lastReturned;
}
}Logic은 단순하다. 단순히 이전/다음에 참조할 수 있는 Node가 있다면 그 값을 반환하는 방식인데, 환형 연결리스트이기 때문에 head / tail을 기반으로 그 이전 / 이후는 뽑을 수 없게 index 값을 저장하여 활용하였다.
하나 하나 이해해보자.
일단 Field의 속성값들을 살펴보면, Int 형으로 nextIndex / prevIndex 를 통해 현재 반환된 Node의 다음 / 이전의 Index 값을 알 수 있도록 구성되었다. 왜 이 값이 필요하냐면 환형 연결리스트 이기 때문에 단순히 해당 Node가 next / previous 참조값을 갖고 있느냐로만 판단하게 되면 영원히 순환하게되기 때문이다.
따라서, nextIndex는 0부터 시작하여 전체 size, 즉 Node의 개수보다 작은 동안 순환할 수 있도록 구성되었고, prevIndex는 가장 이전에 있는 Node가 0번이므로 0보다 크거나 같은 경우까지만 순환할 수 있도록 구성된 것이다.
Node<T> 타입으로 정의된 next / previous / lastReturned는 현재 반환된 Node에서 다음 노드, 이전 노드와 현재 반환된 노드를 표현하기 위해 사용되었다.
hasNext / hasPrevious Method의 이해는 쉽다. 단순히 Index를 기반으로 다음/ 이전 Node가 존재하는지를 판단한다.
next / previous Method는 다음 / 이전 Node를 반환하도록 구성하면서 각각을 기존 참조값에서 하나씩 다음/이전으로 이동시켜주는 코드이다. next method에서 주의할 점은, 현재 반환된 Node가 head 다음일 때부터 previous가 있도록 구성해야 한다는 것이다.
그럼 다음을 통해 이 코드를 테스트할 수 있는 코드를 통해 결과값을 알아보자.
package com.test;
public class LinkedListTest {
public static void main(String[] args){
LinkedListImpl<Integer> linkedList = new LinkedListImpl<>();
linkedList.addFirst(3);
linkedList.addFirst(2);
linkedList.addFirst(1);
linkedList.addFirst(3120);
LinkedListImpl.Iterator iterator = linkedList.getIterator();
while(iterator.hasNext()){
System.out.print(iterator.next().getData() + ", ");
}
System.out.println();
while(iterator.hasPrevious()){
System.out.print(iterator.previous().getData() + ", ");
}
}
}
// 결과
3120, 1, 2, 3,
2, 1, 3120,
잘 동작하는 것을 확인할 수 있다.
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - HashMap 들여다보기(2) (1) | 2020.08.20 |
|---|---|
| 자료구조 - HashMap 들여다보기(1) (0) | 2020.08.19 |
| ArrayList 직접 구현해보기 (Java) (0) | 2020.08.05 |
| 자료구조(Java) - Comparable / Comparator (2) | 2020.07.27 |
| 자료구조(Java) - Iteration (0) | 2020.07.26 |
