차근 차근 알고리즘 공부를 하던 도중 예전 학창시절에 C로 Linked List를 구현하려다가 너무 어려워 포기했던 생각이 나서 지금 구현해봤다.
졸업한지 1년이 지났는데도... 어려웠다
심지어 자바 유틸에 있는 LinkedList의 함수 일부분만 구현했는데 어려웠다. (프로그래밍에 소질이 없나봐 ㅠㅠ)
일단 Linked List가 뭔지 보자면 LinkedList란? 을 들어가보면 된다.
Node라는 이정표로 다른 Node를 포인터로 가르켜 준다.
여기서 c는 포인터가 있는데 java는 없잖아요!! 라고 물을 수 있는데
맞다, 자바에는 포인터가 없다. 하지만 객체는 주소를 참조한다는 형식을 가지고 있다는것을 OOP 언어를 열심히 공부했다면 알고 있을 것이다.
Node라는 객체 안에 또 다른 Node 객체를 넣어 다른 Node를 찾을 수 있게 하면 된다.
말이 너무 어렵다면 코드를 한번 봐보자
Node Class
public class Node{
private Node next;
private String data;
public Node(String data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
}Node 클래스의 맴버 변수로 Node next가 있다.
이 next 변수는 이어진 데이터를 가르키고 있는 거라서
모든 데이터들이 줄줄이 이어져있다.
내가 구현한 함수는 간단하게 크게 나눠보면 추가,삭제,출력 등등(?)이다.
일단 추가 부터 보겠다.
맨 앞에 추가
public void addFirst(String data) {
if(head == null) {
head = new Node(data);
return ;
}
Node newHead = new Node(data);
newHead.setNext(head);
head = newHead;
}맨 뒤에 추가
public void addLast(String data) {
if(head == null) {
head = new Node(data);
return ;
}
Node current = head;
while(current.getNext()!=null) {
current = current.getNext();
}
current.setNext(new Node(data));
}인덱스로 추가
public void add(String data,int num) {
Node one = head;
Node previous = one;
Node newNode = new Node(data);
if(num==0) {
addFirst(data);
return;
}
for(int i=0; i<num; i++) {
previous = one;
one = one.getNext();
}
previous.setNext(newNode);
newNode.setNext(one);
}다음은 추가가 잘 되어있는지 확인 하기 위한 가져오는 함수
전체 가져오기
public List getAll() {
List list = new ArrayList();
Node one = head;
if(head==null){
throw new IndexOutOfBoundsException("잘못된 인덱스 입니다.");
}
list.add(one.getData());
while(one.getNext()!=null) {
one = one.getNext();
list.add(one.getData());
}
return list;
}하나씩 가져오기
public String get(int num) {
Node one = head;
for(int i=0; i<num; i++) {
if(one.getNext()!=null) {
one = one.getNext();
}else{
throw new IndexOutOfBoundsException("잘못된 인덱스 입니다.");
}
}
return one.getData();
}다음은 삭제 함수
맨 앞에 삭제
public void removeFirst() {
if(head==null) {
throw new IndexOutOfBoundsException("삭제할 값이 없습니다.");
}
head = head.getNext();
}맨 뒤에 삭제
public void removeLast() {
if(head==null) {
throw new IndexOutOfBoundsException("삭제할 값이 없습니다.");
}
if(head.getNext()==null) {
head = null;
return;
}
Node current = head;
Node previous = null;
while(current.getNext() !=null) {
previous = current;
current = current.getNext();
}
previous.setNext(null);
}인덱스로 삭제
public void remove(int num) {
Node current = head;
Node previous = null;
Node next = null;
if(num == 0) {
if(head==null) {
throw new IndexOutOfBoundsException("삭제할 값이 없습니다.");
}
head = head.getNext();
return;
}
for(int i=0; i<num; i++) {
if(current.getNext()!=null) {
previous = current;
current = current.getNext();
if(current.getNext()!=null) {
next = current.getNext();
}else{
next = null;
}
}else {
throw new IndexOutOfBoundsException("잘못된 인덱스 입니다.");
}
}
previous.setNext(next);
}Linked List 사이즈를 가져오는 함수
크기 함수 size()
public int size() {
int size;
Node one = head;
if(one==null) {
return 0;
}else{
size = 1;
}
while(one.getNext()!=null) {
one = one.getNext();
size++;
}
return size;
}출력을 위한 toString() 구현
출력 함수 toString()
public String toString() {
if(head == null) {
return "[]";
}
Node one = head;
String str = "[";
while(one.getNext()!=null) {
str+=one.getData()+",";
one = one.getNext();
}
str+=one.getData()+"]";
return str;
}여기까지 LinkedList의 함수 일부분을 구현해 봤다.
추후에 iterator 같은 함수나 다른 함수들을 추가하면 좋을 것 같다.
하지만 아직도 갈길은 멀은 것 같다. 실제 내 코드가 효율성을 가지고 짜여진 것도 아니고
단지 기능을 구현하기 위해서만 만든 코드기 때문에... 사실 제대로 된 LinkedList 함수의 일부분이라고 말하기도 참 뭐한것 같다.
아래는 최종코드이다.
LinkedList.class
public class LinkedList {
Node head;
public void addFirst(String data) {
if(head == null) {
head = new Node(data);
return ;
}
Node newHead = new Node(data);
newHead.setNext(head);
head = newHead;
}
public void addLast(String data) {
if(head == null) {
head = new Node(data);
return ;
}
Node current = head;
while(current.getNext()!=null) {
current = current.getNext();
}
current.setNext(new Node(data));
}
public void add(String data,int num) {
Node one = head;
Node previous = one;
Node newNode = new Node(data);
if(num==0) {
addFirst(data);
return;
}
for(int i=0; i<num; i++) {
previous = one;
one = one.getNext();
}
previous.setNext(newNode);
newNode.setNext(one);
}
public List getAll() {
List list = new ArrayList();
Node one = head;
if(head==null){
throw new IndexOutOfBoundsException("잘못된 인덱스 입니다.");
}
list.add(one.getData());
while(one.getNext()!=null) {
one = one.getNext();
list.add(one.getData());
}
return list;
}
public String get(int num) {
Node one = head;
for(int i=0; i<num; i++) {
if(one.getNext()!=null) {
one = one.getNext();
}else{
throw new IndexOutOfBoundsException("잘못된 인덱스 입니다.");
}
}
return one.getData();
}
public void removeFirst() {
if(head==null) {
throw new IndexOutOfBoundsException("삭제할 값이 없습니다.");
}
head = head.getNext();
}
public void removeLast() {
if(head==null) {
throw new IndexOutOfBoundsException("삭제할 값이 없습니다.");
}
if(head.getNext()==null) {
head = null;
return;
}
Node current = head;
Node previous = null;
while(current.getNext() !=null) {
previous = current;
current = current.getNext();
}
previous.setNext(null);
}
public void remove(int num) {
Node current = head;
Node previous = null;
Node next = null;
if(num == 0) {
if(head==null) {
throw new IndexOutOfBoundsException("삭제할 값이 없습니다.");
}
head = head.getNext();
return;
}
for(int i=0; i<num; i++) {
if(current.getNext()!=null) {
previous = current;
current = current.getNext();
if(current.getNext()!=null) {
next = current.getNext();
}else{
next = null;
}
}else {
throw new IndexOutOfBoundsException("잘못된 인덱스 입니다.");
}
}
previous.setNext(next);
}
public int size() {
int size;
Node one = head;
if(one==null) {
return 0;
}else{
size = 1;
}
while(one.getNext()!=null) {
one = one.getNext();
size++;
}
return size;
}
public String toString() {
if(head == null) {
return "[]";
}
Node one = head;
String str = "[";
while(one.getNext()!=null) {
str+=one.getData()+",";
one = one.getNext();
}
str+=one.getData()+"]";
return str;
}
}
이렇게 Singly Linked List를 구현해 봤는데 많이 어려웠다.
매번 가져다가 쓰기만 해서 내 상태가 이렇게 엉망인줄 몰랐다.
오늘의 결론)
막 가져다가 쓰지만 말고 코딩공부 열심히 하자.... (뿌에에엥)
기록 그리고 기억