자바는 배열 뿐만 아니라 컬렉션 프레임워크라는 이름으로 다양한 자료구조를 제공한다.
배열에서 자료를 찾을때 인덱스를 사용하면 입력,변경,조회의 경우 한번의 계산으로 자료 위치를 찾을 수 있다.
그러나 배열은 필요한 크기를 미리 확보하고, 데이터가 얼마나 추가될지 모르는 상황에서 나머지 공간은 사용되지 않고 낭비된다.
또한, 배열의 앞이나, 중간에 데이터를 추가하면 기존데이터를 뒤로 한칸씩 전부 미뤄야하고, 삭제도 마찬가지이다.
낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 앞이나 중간에 데이터를 추가하거나 삭제할 때 효율적인 자료구조가, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node x = this;
sb.append("[");
while (x != null) {
sb.append(x.item);
if (x.next != null) {
sb.append("->");
}
x= x.next;
}
sb.append("]");
return sb.toString();
}
}저장할 데이터가 item이고, 다음으로 연결할 노드의 참조가 next이다.
//노드 생성하고 연결하기: A -> B -> C
Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");
연결할때는 .next를 통해서 참조값을 넣어준다.
printAll(first);
Node lastNode = getLastNode(first);
int index =2;
Node index2Node = getNode(first,index);
//데이터 마지막에 추가
add(first,"D");private static void printAll(Node node) {
Node x = node;
while(x != null){
System.out.println(x.item);
//마지막 노드의 next 참조값은 null이다.
x = x.next;
}
}마지막 노드의 next 참조값은 null임을 이용해서 while문을 돈다.
private static Node getLastNode(Node node) {
Node x = node;
while(x.next !=null){
x = x.next;
}
//마지막 노드의 x.next는 null이다.
return x;
}private static Node getNode(Node node, int index) {
Node x = node;
for(int i=0;i<index;i++){
x = x.next;
}
//index만큼 for문으로 이동시킨후에 반환
return x;
}index의 노드를 가져오고싶으면 index만큼 for문을 사용해서 이동한 후에 해당 노드를 반환한다.
private static void add(Node node, String param) {
Node lastNode = getLastNode(node);
lastNode.next = new Node(param);
}getLastNode메서드를 호출해서 마지막 노드를 가져오고, .next를 통해서 새로운 노드의 참조값을 대입한다.
MyLinkedList 구현
배열이 아닌 노드를 통해 링크드리스트를 구현하면, 배열 리스트의 단점인, 메모리 낭비, 중간 위치의 데이터 추가에 대한 성능을 어느정도 극복이 가능하다.
public class MyLinkedListV1 {
private Node first;
private int size = 0;
public void add(Object e) {
Node newNode = new Node(e);
if (first == null) {
first = newNode;
}
else {
Node lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node getLastNode() {
Node x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public Object set(int index, Object element) {
Node x = getNode(index);
Object oldValue = x.item;
x.item = element;
return oldValue;
}
public Object get(int index) {
Node node = getNode(index);
return node.item;
}
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public int indexOf(Object o) {
int index = 0;
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
return -1;
}
public int size() {
return size;
}
이번에는 특정 위치에 데이터를 추가하고, 삭제하는 기능을 추가해보자.
첫번째에 노드를 추가하려면
newNode.next = first;
first = newNode;첫번째 위치의 노드를 삭제하려면
first = removeNode.next;
removeNode.item = null;
removeNode.next = null;삭제노드는 GC의 대상이 되어서 제거가 된다.
중간에 노드 추가
Node prev = getNode(index-1);
newNode.next = prev.next;
prev.next = newNode;중간에 노드 삭제
Node prev = getNode(index-1);
prev.next = removeNode.next;
}
removeNode.item = null;
removeNode.next = null;삭제된 노드는 이후 GC에 의해 제거된다.
public class MyLinkedList {
private Node first;
private int size = 0;
public void add(Object e){
Node newNode = new Node(e);
if(first == null){
first = newNode;
}else{
//뒤에다 추가
Node lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node getLastNode(){
Node x = first;
while(x.next !=null){
x = x.next;
}
return x;
}
public void add(int index, Object e){
Node newNode = new Node(e);
if(index==0){
newNode.next = first;
first = newNode;
}else{
Node prev = getNode(index-1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
private Node getNode(int index) {
Node x = first;
for (int i=0;i<index;i++ ) {
x = x.next;
}
return x;
}
public Object remove(int index){
Node removeNode = getNode(index);
Object removedItem = removeNode.item;
if(index ==0){
first = removeNode.next;
}else{
Node prev = getNode(index-1);
prev.next = removeNode.next;
}
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
}
배열리스트는 인덱스를 통해 추가나 삭제를 할때
O(1)시간으로 찾고, 삭제후 한칸씩 밀어야될때 O(n)이 걸린다.
연결리스트는 인덱스를 통해 추가나 삭제를 할때
O(n)시간으로 찾고, 찾은 이후 참조값만 변경하면 되므로 O(1)시간이 걸린다.
앞에 추가하는 경우, 연결리스트가 더 좋다. 배열리스트는 한칸씩 전부 밀어야되기 떄문이다.
반대로, 마지막에 추가하는경우 배열리스트가 더 좋다.
우리가 지금 확인한건, 단일 연결 리스트이다. 즉, 한방향으로만 이동하는 단일 연결 리스트이다.(Node.next값만 가지고 있으므로 다음 노드로밖에 이동하지 못함) 노드 앞뒤로 모두 연결하는 이중 연결 리스트르 사용하면 성능을 더 개선할 수 있다.
뒤에서 설명하지만 자바가 제공하는 연결 리스트는 이중 연결 리스트이다. 또한, 자바가 제공하는 연결리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에서 추가하거나 삭제하는 경우도 O(1)의 성능을 제공한다.
예시
public class Node {
Object item;
Node next; //다음 노드 참조
Node prev; //이전 노드 참조
}마지막 노드를 참조하고있음
public class LinkedList {
private Node first;
private Node last; //마지막 노드 참조
private int size = 0;
}이제는 타입안전성을 위해서 Generic을 사용해보자.
public class MyLinkedList<E> {
private Node<E> first;
private int size = 0;
public void add(E e){
Node<E> newNode = new Node<>(e);
if(first == null){
first = newNode;
}else{
//뒤에다 추가
Node<E> lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node<E> getLastNode(){
Node<E> x = first;
while(x.next !=null){
x = x.next;
}
return x;
}
public void add(int index, E e){
Node<E> newNode = new Node<>(e);
if(index==0){
newNode.next = first;
first = newNode;
}else{
Node<E> prev = getNode(index-1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i=0;i<index;i++ ) {
x = x.next;
}
return x;
}
public E remove(int index){
Node<E> removeNode = getNode(index);
E removedItem = removeNode.item;
if(index ==0){
first = removeNode.next;
}else{
Node<E> prev = getNode(index-1);
prev.next = removeNode.next;
}
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
private static class Node<E>{
E item;
Node<E> next;
public Node(E item){
this.item = item;
}
}
}중첩클래스를 사용하여서 노드를 만들었다.
중첩클래스는 특정 클래스 안에서만 사용될때 주로 사용된다.
Node 클래스는 MyLinkedList안에서만 사용된다 외부에서는 사용할 이유가 없다.
MyLinkedList<String> stringList = new MyLinkedListV3<>();
stringList.add("a");
//stringList.add(123445)오류