Linked List

Linked List

 

 

여러개의 노드로 이루어진 리스트,

노드는 value 값과 함께 다음값으 주소를 가지고 있다.

 

Java 로 구현

class Node {
    int data;
    Node next = null;

    Node(int d) {
        this.data = d;
    }

    void append(int d) {
        Node end = new Node(d);
        Node n = this;

        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }

    void delete(int d) {
        Node n = this;
        while (n.next != null) {
            if (n.next.data == d) {
                n.next = n.next.next;
            } else {
                n = n.next;
            }
        }
    }

    void retrive() {
        Node n = this;
        while (n.next != null) {
            System.out.print(n.data + " => ");
            n = n.next;
        }
        System.out.println(n.data + "=END=");
    }
}

 

Linked List 의 마지막값은 data 를 가지고 next 값을 가지지 않는다.

마지막 값의 위치 판단은 data == null 인곳이다.

 

단점,

특정위치의 값 확인이 다소 느림, 특정위치를 알고 있으면 ArrayList 가 더 빠름

위의 방식에서는 header 인 첫번째 값을 날려버리면 오류가 발생 => 다음 포스트에서 보완

 

점선같은 느낌이라고 할까?