이전 포스팅에서 LinkedList에 대해 알아봤다.
이 포스팅에서는 JAVA로 LinkedList를 구현해보도록 하자.
(LeetCode에서 Design LinkedList를 통해 구현했다.)
Single LinkedList
코드
class MyLinkedList {
int length;
Node head;
class Node {
int val;
Node next;
Node(int x){val = x;}
}
/** Initialize your data structure here. */
public MyLinkedList() {
this.length = 0;
this.head = null;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index < 0 || index >= length) {
return -1;
}
int count = 0;
Node cur = this.head;
while(count != index) {
cur = cur.next;
count++;
}
return cur.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
Node newNode = new Node(val);
newNode.next = this.head;
this.head = newNode;
length++;
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
if(this.length == 0) {
addAtHead(val);
return;
}
Node newNode = new Node(val);
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = newNode;
newNode.next = null;
this.length++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
Node newNode = new Node(val);
if(index == this.length) {
addAtTail(val);
return;
}
if(index == 0) {
addAtHead(val);
return;
}
if(index > this.length) {
return;
}
Node cur = this.head;
int count = 0;
while(count != index - 1) {
cur = cur.next;
count++;
}
newNode.next = cur.next;
cur.next = newNode;
this.length++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index < 0 || index >= this.length) {
return;
}
if(index == 0) {
head = head.next;
}
else {
Node cur = this.head;
int count = 0;
while(count != index - 1) {
cur = cur.next;
count++;
}
cur.next = cur.next.next;
}
this.length--;
}
}initialize
int length;
Node head;
class Node {
int val;
Node next;
Node(int x){val = x;}
}
/** Initialize your data structure here. */
public MyLinkedList() {
this.length = 0;
this.head = null;
}LinkedList의 길이 length와 시작 Node를 갖는 head를 선언했다.
Node에는 data field를 의미하는 val, 다음 Node를 가르키는 next가 있다.
MyLinkedList()를 통해 LinkedList를 초기화한다.
getValue
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index < 0 || index >= length) {
return -1;
}
int count = 0;
Node cur = this.head;
while(count != index) {
cur = cur.next;
count++;
}
return cur.val;
}입력 받은 index에 해당하는 data를 return한다.
입력 받은 index가 invalid하다면 -1을 return한다.
index가 invalid한 경우는 index는 0부터 시작하므로 음수일 경우, index가 LinkedList의 길이를 넘어서는 경우이다.
LinkedList는 특정 요소에 접근하기 위해서는 순차 탐색을 해야한다.
LinkedList의 시작 Node부터 순차 탐색하므로 cur Node를 선언하고 head를 지정한다.
우리가 찾는 index에 도달하기 전까지 while문으로 순차탐색을 진행한다.
(cur Node를 next로 계속 뒤로 이동)
addNode
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
Node newNode = new Node(val);
newNode.next = this.head;
this.head = newNode;
length++;
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
if(this.length == 0) {
addAtHead(val);
return;
}
Node newNode = new Node(val);
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = newNode;
newNode.next = null;
this.length++;
}LinkedList의 head와 tail에 Node를 삽입한다.
head에 삽입
head에 Node를 삽입하는 순서는 다음과 같다.
1. NewNode의 next를 현재 head로 지정한다.
2. head를 NexNode로 바꾼다.
tail에 삽입
tail에 Node를 삽입하려면 우선 LinkedList가 empty인지 확인해야한다.
LinkedList가 empty라면 head에 Node를 삽입하는 것과 같다.
LinkedList가 empty가 아니라면 순차 탐색을 통해 tail을 찾는다.
LinkedList의 tail의 특징은 next가 null이라는 점이다.
(뒤에 가르킬 Node가 없으므로)
찾은 tail의 next를 new Node로 지정한다.
addNode with index
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
Node newNode = new Node(val);
if(index == this.length) {
addAtTail(val);
return;
}
if(index == 0) {
addAtHead(val);
return;
}
if(index > this.length) {
return;
}
Node cur = this.head;
int count = 0;
while(count != index - 1) {
cur = cur.next;
count++;
}
newNode.next = cur.next;
cur.next = newNode;
this.length++;
}주어진 index에 Node를 삽입하는 함수이다.
우선 index가 LinkedList의 length와 같다면 tail에 삽입하는 것과 같다.
index가 0이라면 head에 삽입하는 것과 같다.
index가 LinkedList의 length보다 크다면 invalid한 index이다.
LinkedList에서는 해당 index를 찾기 위해서는 순차탐색을 해야한다.
❗️위에서 tail을 찾기 위해 하던 순차탐색과 뭔가 다르다!
while의 조건문이 다르다!ㅋㅋ
얼핏 생각하면 while(count != index)일거 같은데 우리는 while(count != index - 1)해줄 것이다.
그 이유는 위의 그림을 보면 조금 이해할 수 있을거다.
내가 원햐는 index에 Node를 삽입하기 위해서는 index-1, index+1에 해당하는 Node와 관련 있기 때문이다.
index-1 Node의 next가 New Node의 next가 될 것이고,
index-1 Node의 next는 New Node가 될 것이기 때문이다.
deleteNode with index
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index < 0 || index >= this.length) {
return;
}
if(index == 0) {
head = head.next;
}
else {
Node cur = this.head;
int count = 0;
while(count != index - 1) {
cur = cur.next;
count++;
}
cur.next = cur.next.next;
}
this.length--;
}
}입력 받은 index가 0보다 작거나, LinkedList의 length랑 같거나 크면 invalid한 index이다.
입력 받은 index가 0이라면 head만 옮겨주면 된다.
index가 0이 아니라면 순차탐색으로 우리가 삭제하고자 하는 index의 앞 Node를 찾으면 된다.
그리고 우리가 찾은 Node의 next를 수정해주면 된다.
마무리
자료구조를 다시 재정비하고 싶어서 시작한 시리즈인데 생각보다 재밌다.
LeetCode에 잘 정리되어 있었고, 코스를 따라서 하다보면 LinkedList에 대한 개념과 기본 문제풀이 능력을 기를 수 있을거 같다.
내일의 PS는 LeetCode에서 제공해주는 LinkedList 문제를 푸는거로 정했다!ㅋㅋ
그럼 오늘도 이만!👋
