[해당 포스트는 개인적으로 공부를 하고 차후에 참고용으로 하고자 작성한 것입니다.
따라서 잘못된 부분이나 부족한 부분이 있을 수 있기에 참고하시기 바랍니다.]
저번 포스팅으로 Linked List에 대한 실습을 해보았었다.
이번 시간엔 Linked List를 직접 구현해보고 테스트해보는 실습을 하였다. 그러나 추가적인 지시사항이 있었다 하면 Doubly Linked List로 구현하고, Integer 한정으로 처리할 수 있는 Linked List를 구현하며, CRUD를 만족하라고 하셨기에 조건에 맞춰 구현을 했다.
이번 실습에선 addLast와 removeLast 구현은 생략했다.
이건 각자 소스코드를 참조하여 구현하면 될 듯하다.
자세한 설명은 주석으로 다 적어놨으니 참고하여 읽으면 될 듯하다.
Node Class
Node Class는 MyLinkedList의 Inner Class로 넣었으므로 private Type로 설정.
맨 밑에 Full Source Code를 참조하자.
/**
* 새로운 노드를 추가할 수 있도록
* 내부 Class로 Node를 만든다.
* */
private class Node{
private Node nextNode;
private Node prevNode;
private int data;
/**
* Node 생성자 호출 작업
* 해당 Node객체를 초기화 시킨다.
* @param data 새로 추가할 데이터
* */
public Node(int data) {
this.data = data;
this.nextNode = null;
this.prevNode = null;
}
}CRUD (Create)
/**
* Doubly Linked List 맨 앞에 새로운 Node를 추가하는 Method.
* 1. 새로운 Node를 추가하면 Node객체를 생성한다.
* 2. 이미 head가 Node를 가르키고 있다면 앞 자리에 Node를 삽입한다.
* 3. head를 새로 들어온 Node의 인스턴스 정보를 저장한다.
* 4. 만약 새로운 Node의 Next가 null일 경우 tail에 head를 추가한다.
* 5. Doubly Linked List크기를 증가시킨다.
* @param data 새로 추가할 데이터
* */
public void addFirst(int data) {
Node newNode = new Node(data);
/*
* 이미 head에 데이터가 있는 경우.
* 1. head가 null을 가리키고 있지 않다.
* 2. 다음 새로 추가되는 Node의 Next를 기존에 있던 Node의
* 인스턴스 정보를 새로운 Node의 Next로 가르킨다.
* 3. head는 가장 앞 자리 Node의 인스턴스 정보를 가진다.
* 4. 기존에 있던 Node의 Prev를 새로운 노드로 설정한다.
* */
if (head != null) {
newNode.nextNode = head;
head.prevNode = newNode;
}
/*
* head의 Next는 새로 들어오는 Node의 인스턴스정보를 가진다.
* */
head = newNode;
/*
* 만약 새로운 Node의 Next를 가르키는 정보가 없다면,
* head에 tail을 넣어준다.
* */
if (head.nextNode == null) {
tail = head;
}
size++;
}/**
* 원하는 Index에 data를 추가시켜주는 Method.
* @param index Linked List에 들어갈 Index 번호
* @param data Node에 추가할 Data
* */
public void add(int index, int data) {
/*
* 만약 Index가 0이면, 비어있다는 뜻.
* 따라서 제일 처음자리에 Node를 생성하여 Data를 넣는다.
* 만약 Index가 0이 아니면, 이미 Node가 있다는 뜻.
* 새로운 Node를 생성하여 Data를 넣는다.
* 새로 추가된 Node의 Prev를 가리키기 위해
* index - 1번째의 Node Instance 정보를 가져온다.
* 새로운 Node의 Next를 가리키기 위해
* 이전 Node에 있던 Next를 가져온다.
* */
if (index == 0) {
addFirst(data);
}else {
Node newNode = new Node(data);
Node prevNode = getNode(index - 1);
Node nextNode = prevNode.nextNode;
newNode.prevNode = prevNode;
newNode.nextNode = nextNode;
prevNode.nextNode = newNode;
nextNode.prevNode = newNode;
size++;
}
}CRUD (Read)
/**
* Linked List에 저장된 Data의 항목을 출력하는 Method.
* 만약 size가 0이면 Linked List가 비어있으므로, 바로 return 한다.
* 만약 size가 0이 아니라면, Node를 순차적으로 탐색하며
* StringBuffer에 넣어준다.
* @return result 순환하며 저장된 Node list를 반환한다.
* */
public String toString() {
StringBuffer result = new StringBuffer("[");
if (size != 0) {
Node node = head;
result.append(node.data);
while (node.nextNode != null) {
node = node.nextNode;
result.append(", ");
result.append(node.data);
}
}
result.append("]");
return result.toString();
}CRUD (Update)
/**
* Index에 위치한 Node의 Data를 변경하는 Method.
* 만약 크기가 0이면 Linked List가 비어있으므로, 바로 return 한다.
* 만약 크기가 0이 아니면 Linked List에 Node가 존재하므로,
* 해당 Node의 인스턴스를 가져와 data를 교체한다.
* @param index Index에 속하는 Node
* @param data 변경하고자 하는 Data
* @return boolean 정상적으로 변경됬는지에 대한 Boolean.
* */
public boolean update(int index, int data) {
if (size == 0)
return false;
Node node = getNode(index);
node.data = data;
return true;
}CRUD (Delete)
/**
* 제일 첫 번째 Node를 삭제하는 Method.
* 만약 크기가 비어있다면 Linked List가 비어있으므로, 바로 return 한다.
* 만약 크기가 0이 아니면 Linked List에 Node가 있으므로,
* head가 가리키던 Node 인스턴스를 가져온다.
* head는 삭제되던 Node가 Next하던 Tail로 가리키고
* 삭제되는 Node의 prev를 null로 설정하여 연결을 끊는다.
* @return boolean 정상적으로 삭제됬는지에 대한 Boolean.
* */
public boolean removeFirst() {
if (size == 0)
return false;
Node removeNode = head;
head = removeNode.nextNode;
head.prevNode = null;
size--;
return true;
}/**
* 해당하는 Index의 Node를 제거하는 Method.
* 만약 크기가 0이면, Linked List에 제거할 Node가 없기에 바로 return.
* 만약 index가 0이면, 제일 첫 번째 Node를 제거하는 removeFirst() 호출.
* 만약 index가 0이 아니면, 제거하는 Node의 인스턴스를 가져온다.
* prev와 next Node 정보를 가져온 후,
* 이전 Node는 삭제하는 Node의 next를 update시키고,
* 삭제하는 Node의 다음 Node의 prev를 update시킨다.
* @return boolean 정상적으로 삭제됬는지에 대한 Boolean.
* */
public boolean remove(int index) {
if (size == 0)
return false;
if (index == 0) {
return removeFirst();
} else {
Node removeNode = getNode(index);
Node prevNode = removeNode.prevNode;
Node nextNode = removeNode.nextNode;
prevNode.nextNode = nextNode;
nextNode.prevNode = prevNode;
size--;
return true;
}
}Full Source Code
public class MyLinkedList {
private Node head;
private Node tail;
private int size;
/**
* 새로운 Linked List를 생성하면,
* 크기 0으로 초기화 시칸다.
* */
public MyLinkedList() {
size = 0;
}
/**
* 새로운 노드를 추가할 수 있도록
* 내부 Class로 Node를 만든다.
* */
private class Node{
private Node nextNode;
private Node prevNode;
private int data;
/**
* Node 생성자 호출 작업
* 해당 Node객체를 초기화 시킨다.
* @param data 새로 추가할 데이터
* */
public Node(int data) {
this.data = data;
this.nextNode = null;
this.prevNode = null;
}
}
/**
* Doubly Linked List 맨 앞에 새로운 Node를 추가하는 Method.
* 1. 새로운 Node를 추가하면 Node객체를 생성한다.
* 2. 이미 head가 Node를 가르키고 있다면 앞 자리에 Node를 삽입한다.
* 3. head를 새로 들어온 Node의 인스턴스 정보를 저장한다.
* 4. 만약 새로운 Node의 Next가 null일 경우 tail에 head를 추가한다.
* 5. Doubly Linked List크기를 증가시킨다.
* @param data 새로 추가할 데이터
* */
public void addFirst(int data) {
Node newNode = new Node(data);
/*
* 이미 head에 데이터가 있는 경우.
* 1. head가 null을 가리키고 있지 않다.
* 2. 다음 새로 추가되는 Node의 Next를 기존에 있던 Node의
* 인스턴스 정보를 새로운 Node의 Next로 가르킨다.
* 3. head는 가장 앞 자리 Node의 인스턴스 정보를 가진다.
* 4. 기존에 있던 Node의 Prev를 새로운 노드로 설정한다.
* */
if (head != null) {
newNode.nextNode = head;
head.prevNode = newNode;
}
/*
* head의 Next는 새로 들어오는 Node의 인스턴스정보를 가진다.
* */
head = newNode;
/*
* 만약 새로운 Node의 Next를 가르키는 정보가 없다면,
* head에 tail을 넣어준다.
* */
if (head.nextNode == null) {
tail = head;
}
size++;
}
/**
* 원하는 Index에 data를 추가시켜주는 Method.
* @param index Linked List에 들어갈 Index 번호
* @param data Node에 추가할 Data
* */
public void add(int index, int data) {
/*
* 만약 Index가 0이면, 비어있다는 뜻.
* 따라서 제일 처음자리에 Node를 생성하여 Data를 넣는다.
* 만약 Index가 0이 아니면, 이미 Node가 있다는 뜻.
* 새로운 Node를 생성하여 Data를 넣는다.
* 새로 추가된 Node의 Prev를 가리키기 위해
* index - 1번째의 Node Instance 정보를 가져온다.
* 새로운 Node의 Next를 가리키기 위해
* 이전 Node에 있던 Next를 가져온다.
* */
if (index == 0) {
addFirst(data);
}else {
Node newNode = new Node(data);
Node prevNode = getNode(index - 1);
Node nextNode = prevNode.nextNode;
newNode.prevNode = prevNode;
newNode.nextNode = nextNode;
prevNode.nextNode = newNode;
nextNode.prevNode = newNode;
size++;
}
}
/**
* 해당하는 Index의 Node 인스턴스를 가져오는 Method.
* @param index Linked List에 속해있는 Node의 index.
* @return node Index에 속하는 Node.
* */
private Node getNode(int index) {
/*
* 만약 index의 크기가 전체 크기의 절반보다 작으면
* head에서 부터 검색을 시작한다.
* index 위치까지 반복하여 해당 Node의 정보를 node에 저장한다.
* 만약 index의 크기가 전체 크기의 절반보다 크면
* tail에서 부터 검색을 시작한다.
* */
if (index < size / 2) {
Node node = head;
for (int i = 0; i < index; i++) {
node = node.nextNode;
}
return node;
}else {
Node node = tail;
for (int i = size - 1; i > index; i--) {
node = node.prevNode;
}
return node;
}
}
/**
* 제일 첫 번째 Node를 삭제하는 Method.
* 만약 크기가 비어있다면 Linked List가 비어있으므로, 바로 return 한다.
* 만약 크기가 0이 아니면 Linked List에 Node가 있으므로,
* head가 가리키던 Node 인스턴스를 가져온다.
* head는 삭제되던 Node가 Next하던 Tail로 가리키고
* 삭제되는 Node의 prev를 null로 설정하여 연결을 끊는다.
* @return boolean 정상적으로 삭제됬는지에 대한 Boolean.
* */
public boolean removeFirst() {
if (size == 0)
return false;
Node removeNode = head;
head = removeNode.nextNode;
head.prevNode = null;
size--;
return true;
}
/**
* 해당하는 Index의 Node를 제거하는 Method.
* 만약 크기가 0이면, Linked List에 제거할 Node가 없기에 바로 return.
* 만약 index가 0이면, 제일 첫 번째 Node를 제거하는 removeFirst() 호출.
* 만약 index가 0이 아니면, 제거하는 Node의 인스턴스를 가져온다.
* prev와 next Node 정보를 가져온 후,
* 이전 Node는 삭제하는 Node의 next를 update시키고,
* 삭제하는 Node의 다음 Node의 prev를 update시킨다.
* @return boolean 정상적으로 삭제됬는지에 대한 Boolean.
* */
public boolean remove(int index) {
if (size == 0)
return false;
if (index == 0) {
return removeFirst();
} else {
Node removeNode = getNode(index);
Node prevNode = removeNode.prevNode;
Node nextNode = removeNode.nextNode;
prevNode.nextNode = nextNode;
nextNode.prevNode = prevNode;
size--;
return true;
}
}
/**
* Index에 위치한 Node의 Data를 변경하는 Method.
* 만약 크기가 0이면 Linked List가 비어있으므로, 바로 return 한다.
* 만약 크기가 0이 아니면 Linked List에 Node가 존재하므로,
* 해당 Node의 인스턴스를 가져와 data를 교체한다.
* @param index Index에 속하는 Node
* @param data 변경하고자 하는 Data
* @return boolean 정상적으로 변경됬는지에 대한 Boolean.
* */
public boolean update(int index, int data) {
if (size == 0)
return false;
Node node = getNode(index);
node.data = data;
return true;
}
/**
* Linked List에 저장된 Data의 항목을 출력하는 Method.
* 만약 size가 0이면 Linked List가 비어있으므로, 바로 return 한다.
* 만약 size가 0이 아니라면, Node를 순차적으로 탐색하며
* StringBuffer에 넣어준다.
* @return result 순환하며 저장된 Node list를 반환한다.
* */
public String toString() {
StringBuffer result = new StringBuffer("[");
if (size != 0) {
Node node = head;
result.append(node.data);
while (node.nextNode != null) {
node = node.nextNode;
result.append(", ");
result.append(node.data);
}
}
result.append("]");
return result.toString();
}
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addFirst(4);
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
System.out.println(list.toString());
list.add(2, 25);
System.out.println(list.toString());
list.remove(1);
System.out.println(list.toString());
list.update(3, 13);
System.out.println(list.toString());
}
}'Coding Language > Java' 카테고리의 다른 글
| [기억을 되돌리며#2] 문자열을 붙여주는 StringBuilder (0) | 2021.07.01 |
|---|---|
| [기억을 되돌리며#1] Buffered Reader를 이용한 데이터 입출력 (0) | 2021.06.29 |
| 아무거나 글올리기 챌린지 (0) | 2021.06.29 |
| [Java] Linked List를 이용하여 Collections의 sort Method를 사용해보자. (1) | 2019.07.23 |
| [Java] Lambda 식을 이용하여 코드 줄이기 (0) | 2019.07.18 |