시간이 NullNull
[JAVA] [자료구조] Linked List (구현 및 설명) 본문
전체 코드는 맨 아래에 첨부해 두었습니다.
Java 에서 기본적으로 Linked List를 제공해주기 때문에 일반적으로 시험을 제외하고는 잘 구현하지 않는 편이다.
C언어에 대해서 자세히 모르지만 아마도 추축컨데 C언어에서 Linked List를 구현한다면
다음 Node를 주소값으로 가르켜 데이터를 가져올 것으로 예측된다.
하지만 Java에서는 주소값이 없기때문에 다음과 같은 방식으로 Linked List를 구현한다.
보통 Head와 Data, Tail로 구현하여
Head는 앞의 객체 Data는 현재 값 Tail은 다음 객체를 가르키도록 구현하지만
개인적인 생각으로는 Linked List에서 앞으로 가는 경우는 없기 때문에 Data와 Tail만 구현하면 된다고 생각한다.
( 필자의 개인 습관으로 Data와 next로 적도록 하겠다. )
1. Data를 가지는 Field와 Next를 가리킬 객체를 넣어준다.
2. Data만 받을 수도 있고 Data와 Next를 함께 받을수도 있기에 생성자는 총 3개로 만들어준다.
static class link<U>{
private U data;
private link<U> next;
link(){ }
link(U data){
this.data = data;
}
link(U data, link<U> next){
this.data = data;
this.next = next;
}
}U라는 것은 String이 올수도 Integer가 올수도 우리가 임의로 만든 객체가 올수도 있게 한 것으로
Data에 어떤 값이든 들어갈 수 있도록 하였다.
Trie 알고리즘 글에서 보았겠지만 객체의 Field를 그 자신 객체를 넣어 줌으로써 연속된 객체를 만들 수 있다.
( ex. (0번)Data = 0,Next = (1번객체), (1번)Data = 1, Next = (2번객체)..... )
이해가 안된다면 뒤에 다른 구현한 함수들을 보며 조금 더 이해할 수 있을 것이다.
실제 Java 라이브러리에 있는 LinkedList의 함수들을 다 구현할 수도 있지만
나는 꼭 필요한 Add, Delete, IsEmpty, Size, toString 만 구현하였다. ( 물론 Override 하여 다양한 경우를 대비하였다. )
1. isEmpty()
isEmpty의 경우 간단하다. 크게 두가지 방법이 있는데
Size를 통해 확인하는 방법과 객체 자체가 존재하는 지를 체크하는 방법이다.
Size를 통해 확인하더라도 Size에서 객체가 있는지를 확인하는 작업이 들어가기 때문에
나의 경우 객체의 존재 유무로 isEmpty를 만들어 주었다.
코드는 심플하여 다른 설명은 하지 않겠다.
boolean isEmpty() {
return first == null;
}first가 무엇인가에 대해서 의문이 생길 수 있지만 전체 코드를 본다면 이해가 갈 것이다.
2. Size()
Size의 경우만 보게 되더라도 앞서 설명한 next가 다음 객체를 가리키는 것을 쉽게 이해할 수 있는데
while문을 돌며 next의 유무를 확인하고 next가 null, 즉 없다면 while문을 빠져나와
갯수를 리턴 시켜준다.
여기서 확인해야할 주요 포인트는 node = node.next이다.
link 라는 클래스의 field에 next는 link라는 객체를 넣어줌으로써 0번 객체에서 1번 객체로 넘어가는 것이 가능해진다.
이 부분을 이해한다면 어지간한 자바의 알고리즘 구현에 대해서 다 알 수 있을 것이다.
int Size(){
link<T> node = first;
int cnt = 0;
if(!isEmpty()) {
while(true) {
cnt++;
if(node.next == null) {
break;
}
node = node.next;
}
}
return cnt;
}여기서 T에 대해 의문이 생길 수 있는데 전체 코드를 보면 아까 U와 같다는 것을 알 수 있다.
Data 타입이라고 만 생각하고 넘어가면 된다.
3. add()
add의 경우 이해를 돕기위해 무조건 뒤에 넣는 것만 만드는 것이 아닌
원하는 index에 Data를 삽입할 수 있도록 구현하여 하나를 더 추가 해보았다.
if문들의 경우 index 에러 등 잘못된 것을 방지하기 위해 넣었고
index error를 나타내는 print문 밑에 for문은 결과를 보여줄때 print문이 어떻게 나오는지 확실히 보여주기위해
임의의 딜레이를 넣어준 것이다.
처음에 보여줄 것은 인덱스가 없이 맨 끝에 데이터를 넣는것이다.
void add(T element){
if(isEmpty()) {
first = new link<>(element);
return;
}
link<T> node = first;
while(true) {
if(node.next == null) {
node.next = new link<T>(element);
break;
}
node = node.next;
}
}first가 없다면 first를 만들면서 값을 넣어주고
first가 있다면 next가 없는 객체를 찾아가 즉, 맨 마지막 객체로 가 next에 새로운 값을 넣어주게 된다.
위에서 사이즈를 볼때도 그렇고 지금 add에서도 의문이 하나 들 수가 있다.
node = node.next를 실행하게 되면 first라는 객체에 다른 값이 덮힌다거나 아무 문제가 일어 나지 않는 것인가?
이해가 어려운 분들이 있을 수 있기에 쉽게 설명을 하면
첫번째로, 우리는 first = first.next라던가 다른 작업을 하지 않았다. 그러므로 처음의 first 객체는 그대로 유지되게 된다.
두번째로, node = first를 담아 first의 값을 가져오고 이때 node는 first의 주소값을 공유하게 된다.
하지만 node == first가 아니라 node라는 틀에 first를 잠시 담아두었다고 생각하면 이해하기 쉬울 것 같다.
쓰면서도 더 이해하기 힘든 것인가 다른 방법이 없을 까 생각이 들지만 이게 최선이라고 생각이 든다.
여튼, 그래서 node = node.next를 하게 되면
맨처음을 기준으로 node라는 틀에 first의 next를 넣게 된다.
node(first).next값을 가져와 다시 node에 있는 first를 빼네고 node.next를 넣는 것이다.
index를 주는 add의 경우 코드는 다음과 같다.
void add(int index, T element){
if(isEmpty()) {
if(index == 0) {
first = new link<T>(element);
}else {
System.err.println("Index Error");
for(int i=0; i<10; ++i) { }
return;
}
}else {
if(index > Size()) {
System.err.println("Index Error");
for(int i=0; i<10; ++i) { }
return;
}else {
if(index == 0) {
link<T> node = new link<T>(element, first);
first = node;
}else {
link<T> node = first;
int cnt = 0;
while(true) {
if(cnt == index-1) {
link<T> temp = new link<T>(element, node.next);
node.next = temp;
break;
}
++cnt;
node = node.next;
}
}
}
}
}여기서 눈 여겨 볼 점은 왜 cnt == index - 1 일때 작업을 하냐 인데
쉽게 생각해보면 1번째 자리에 값을 넣을때
0번째 자리의 next에 내가 새로 만든 객체를 넣어주고 그 객체의 뒤에 원래 1번째 있던 아이를 붙여주는 것이다.
정말 내가 ppt로 도형을 그려 쉽게 설명하기 싫어서 이렇게 텍스트만 남기는 것은 아니다...
4. delete()
delete도 마찬가지로 가장 앞에 것을 지우는것 혹은 index번째 데이터를 지우는 것으로 하였는데
add를 이해하였다면 delete는 같은 방식이기에 코멘트를 더 달지 않겠다.
void delete() {
if(isEmpty()) {
return;
}
first = first.next;
}void delete(int index) {
if(isEmpty() || index >= Size()) {
System.err.println("Index Error");
for(int i=0; i<10; ++i) { }
return;
}
int cnt = 0;
link<T> node = first;
while(true) {
if(cnt == index-1) {
node.next = node.next.next;
break;
}
node = node.next;
cnt++;
}
}5. toString()
toString의 경우 결과 값을 보여줄때 편하게 보여주기 위해 그냥 만든 것이며 생략하여도 아무 문제가 없다.
6. 전체코드
public class linked_list<T> {
static class link<U>{
private U data;
private link<U> next;
link(){ }
link(U data){
this.data = data;
}
link(U data, link<U> next){
this.data = data;
this.next = next;
}
}
private link<T> first;
linked_list(){
this.first = null;
}
boolean isEmpty() {
return first == null;
}
void add(int index, T element){
if(isEmpty()) {
if(index == 0) {
first = new link<T>(element);
}else {
System.err.println("Index Error");
for(int i=0; i<10; ++i) { }
return;
}
}else {
if(index > Size()) {
System.err.println("Index Error");
for(int i=0; i<10; ++i) { }
return;
}else {
if(index == 0) {
link<T> node = new link<T>(element, first);
first = node;
}else {
link<T> node = first;
int cnt = 0;
while(true) {
if(cnt == index-1) {
link<T> temp = new link<T>(element, node.next);
node.next = temp;
break;
}
++cnt;
node = node.next;
}
}
}
}
}
void add(T element){
if(isEmpty()) {
first = new link<>(element);
return;
}
link<T> node = first;
while(true) {
if(node.next == null) {
node.next = new link<T>(element);
break;
}
node = node.next;
}
}
void delete(int index) {
if(isEmpty() || index >= Size()) {
System.err.println("Index Error");
for(int i=0; i<10; ++i) { }
return;
}
int cnt = 0;
link<T> node = first;
while(true) {
if(cnt == index-1) {
node.next = node.next.next;
break;
}
node = node.next;
cnt++;
}
}
void delete() {
if(isEmpty()) {
return;
}
first = first.next;
}
int Size(){
link<T> node = first;
int cnt = 0;
if(!isEmpty()) {
while(true) {
cnt++;
if(node.next == null) {
break;
}
node = node.next;
}
}
return cnt;
}
@Override
public String toString() {
String str = "";
link<T> node = first;
if(!isEmpty()) {
while(true) {
str += node.data+" ";
if(node.next == null) {
break;
}
node = node.next;
}
}
return str;
}
}
7. 테스트를 위한 코드
public class linkTest {
public static void main(String[] args) {
linked_list<Integer> list = new linked_list<>();
for(int i=0; i<10; ++i) {
list.add((int)(Math.random()*10));
}
System.out.println("First list");
System.out.println("list : "+list.toString()+"\n");
list.delete();
System.out.println("Delete First Data");
System.out.println("list : "+list.toString()+"\n");
list.delete(3);
System.out.println("Delete third Data");
System.out.println("list : "+list.toString()+"\n");
list.delete(8);
System.out.println("Delete eight Data");
System.out.println("list : "+list.toString()+"\n");
for(int i=0; i<3; ++i) {
int index = (int)(Math.random()*10);
int value = (int)(Math.random()*10);
list.add(index, value);
System.out.println("index : "+index+" / Add :"+value);
System.out.println("list : "+list.toString()+"\n");
}
}
}
편의상 Integer 값을 넣었으며 랜덤 난수를 넣어 보기 편하도록 하였다.
index 값을 바꾸어 실험해 보거나 데이터를 더 넣거나 빼본다면 더 이해가 빠를 것이라 생각이 된다.
오랜만에 블로그 글을 남기게 되었는데 사실 다른사람들이 왜 내 블로그에 오는 지 모르겠다.
원래는 취업을 위해서 내 공부+기록남기기 용도였는데 나름 사람들이 오자 신기해서 글을 더 쓰기 시작한 것 같다.
지금은 대부분 취업하여 사라진 취업스터디에서는 notion을 잘 활용하여 코드를 잘 공유하여서...
사실 이건 그 스터디원들도 모르는 나만의 공간이다.
이 글도 작성하지 않을 뻔하였으나 우연히 링크드 리스트를 만들어야하는 이유가 생겨 만들다 보니
자료구조로써 정리하여 작성한다.
누가 보게 될지는 모르겠으나 이 글을 보고 도움이 되어 꼭 취업에 성공하였으면 좋겠다.
(학점을 조금이나마 잘받는 것도 취업에 도움이 되긴하니깐...)