단순연결리스트(Simple LinkedList)란?
단순연결리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고,
각 노드의 포인터는 다음 노드를 가르키는 하나의 참조만을 갖는다.
다음 노드의 참조만 가지고 있으므로 노드의 접근은 한 방향으로만 가능하다.
public class SimpleLinkedList_Rz {
class SimpleLinkedList{
private Node head;
private int size;
public SimpleLinkedList(){
head = new Node(null);
size = 0;
}
private class Node{
private Object data; // 데이터가 저장될 필드
private Node nextNode; // 다음 노드를 가르키는 필드
public Node(Object input){
this.data = input;
this.nextNode = null;
}
public String toString(){
return String.valueOf(this.data);
}
}
public Node getNode(int index){ // index 위치에 있는 노드를 반환한다.
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index : " + index + ", Size : " + size);
}
Node node = head.nextNode;
for(int i = 0; i < index; i++){
node = node.nextNode;
}
return node;
}
public Object get(int index){ // index 위치에 있는 데이터를 반환한다.
return getNode(index).data;
}
public Object getFirst(){ // 첫번째 노드를 반환한다.
return get(0);
}
public int getNodeIndex(Object data){ // 해당 데이터의 index 위치를 반환한다.
if(size <= 0){
return -1;
}
Node node = head.nextNode;
int index = 0;
while(node != null){
if(data.equals(node.data)){
return index;
}
node = node.nextNode;
index++;
}
return -1;
}
public void addFirst(Object data){ // 첫번째 위치에 데이터를 삽입한다.
Node newNode = new Node(data);
newNode.nextNode = head.nextNode;
head.nextNode = newNode;
size++;
}
public void add(int index, Object data){ // index 위치에 데이터를 삽입한다.
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index : " + index + ", Size : " + size);
}
if(index == 0){
addFirst(data);
return;
}
Node prevNode = getNode(index - 1);
Node nextNode = prevNode.nextNode;
Node newNode = new Node(data);
prevNode.nextNode = newNode;
newNode.nextNode = nextNode;
size++;
}
public void addLast(Object data){ // 마지막 위치에 데이터를 삽입한다.
add(size, data);
}
public Object removeFirst(){ // 첫번째 노드를 제거하고 해당 노드를 반환한다.
Node delNode = getNode(0);
head.nextNode = delNode.nextNode;
size--;
return delNode.data;
}
public Object remove(int index){ // index에 해당하는 노드를 제거하고 해당 노드를 반환한다.
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index : " + index + ", Size : " + size);
}
if(index == 0){
return removeFirst();
}
Node prevNode = getNode(index - 1);
Node delNode = getNode(index);
prevNode.nextNode = delNode.nextNode;
size--;
return delNode.data;
}
public Object removeLast(){ // 마지막 노드를 제거하고 해당 노드를 반환한다.
return remove(size - 1);
}
public int getSize(){ // 링크드리스트의 사이즈를 반환한다.
return size;
}
}
}
