Single Linked List

• Single LinkedList

 

node, next로 만 이루어진 구조

 

원소마다 node에 값을 가지고 다음 원소를 가리키는 link를 통해서 연결한다

firstNode = null, lastNode  = null로 초기화하고 시작한다

순차적으로 접근할때 Iterator를 사용해 효율적으로 관리가 가능하다

 

addLast 연산 O(1)

size가 0이면 firstNode를 newNode로

그게 아니면 기존 lastNode.next를 newNode로 바꾸고 lastNode를 newNode로  변경

 

addFirst 연산 O(1)

size가 0이면 lastNode를 newNode로

그게 아니면 firstNode를 newNode로 하고 firstNode.next를 기존 firstNode로

 

get 연산 O(N)

특정 위치에 노드에 접근하기 위해서 선형탐색을 하면서 해당 위치까지 접근해야한다

링크드리스트에서 원소 각각에 get을 사용하면 n2이 되는 참사가 일어날 수 있으니

순차적 접근은 ListIterator를 사용하자 

 

insert 연산 ,

insert(idx) 연산 - 해당 인덱스까지 타고 가서 연결 O(N)

insert(node) 연산 - 새 노드 생성, 새 노드의 next를 node 노드로 연결 O(1)

 

 

remove 연산

특정 인덱스 노드를 삭제하고 싶을때 는 선형접근을 해야된다, remove(node) - O(n)

특정 노드 다음 노드를 삭제하고 싶을때  - O(1)이다
특정 노드(여기선 prevNode)의 다음 노드가 없으면 바로 리턴
prevNode.next = prevNode.next.next 로 기존 prevNode.next를 가리키는 노드가 없게 만들 수 있다

가리키는 노드가 없으면? GC가 수거해간다

iterator 가 있는 경우에는 LinkedList의 insert, remove 연산이 o(1)만에 가능하다

 

구현해보자

public class MySingleLinkedList<E> {
    private int size = 0;
    private Node<E> firstNode = null;
    private Node<E> lastNode = null;

    //각각의 노드는 현재 노드 데이터와, 다음 노드를 가르키는 포인터로 이루어져 있다
    public static class Node<E> {
        E item;
        Node<E> next;
        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

    //맨 앞에 넣을때는
    public void addFirst(E element) {
        Node<E> newNode = new Node<>(element, firstNode);
        // 비어있을때 노드를 추가하면 newNode가 first이자 last가 되야한다
        // lastNode를 newNode로 해야 add 연산할때 last.next로 접근 가능
        if (size == 0) lastNode = newNode;
        firstNode = newNode;
        size++;
    }

    //리스트 마지막에 추가하는 연산
    public void add(E element) {
        Node<E> newNode = new Node<>(element, null);
        if (size == 0) firstNode = newNode;
        else lastNode.next = newNode;
        lastNode = newNode;
        size++;
    }

    // 노드를 반환, 시간복잡도 O(N)
    public Node<E> getNode(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
       // 처음부터 idx만큼 이동하면서 idx번째 노드를 찾는다
        Node<E> currentNode = firstNode;
        for (int i = 0; i < idx; i++)
            currentNode = currentNode.next;
        return currentNode;
    }

    // 노드의 데이터를 반환, 시간복잡도 O(N)
    public E get(int idx) {
        return getNode(idx).item;
    }

    // 특정 노드의 데이터를 변경, O(N)
    public void set(int idx, E element) {
        Node<E> targetNode = getNode(idx);
        targetNode.item = element;
    }

    //중간 삽입, 특정 노드 다음에 새 노드를 넣기
    //링크를 끊기전에 prev.next를 newnode.next에 넣어줘야 한다. 순서 중요 

    public void insert(Node<E> prevNode, E element) {
        Node<E> newNode = new Node<>(element, prevNode.next);
        prevNode.next = newNode;
        // 새 노드의 다음값이 없으면 마지막에 추가한 것
        if (newNode.next == null)
            lastNode = newNode;
        size++;
    }

    public void insert(int idx, E element) {
        if (idx < 0 || idx > size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        if (idx == 0) addFirst(element);
        else if (idx == size) add((element));
        // idx가 size나 0이 아닌 경우에는 idx-1 위치에 있는 노드 다음에
        // newNode를 삽입해서 newNode가 idx번째 위치하게 해준다
        else insert(getNode(idx - 1), element);
    }

    public void removeFirst() {
        if (firstNode != null) {
            firstNode = firstNode.next;
            //노드가 하나만 있을때는 lastnode만 남아있다
            if (firstNode == null)
                lastNode = null;
            size--;
        }
    }

    //이전 노드를 받아와서 이전 노드를 삭제하려는 노드의 다음으로 연결한다
    // 다음 노드가 없으면? last노드를 삭제하는 경우, 이전 노드를 lastNode로 바꾼다
    public void removeNext(Node<E> prevNode) {
        if (prevNode.next != null) {
            prevNode.next = prevNode.next.next;
            if (prevNode.next == null)
                lastNode = prevNode;
            size--;
        }
    }

    public void remove(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        if (idx == 0) removeFirst();
        else removeNext(getNode(idx - 1));
    }

    public Node<E> getFirstNode() {
        return firstNode;
    }

    public Node<E> getLastNode() {
        return lastNode;
    }

    public int size() {
        return size;
    }

    //깔끔하게 [1, 3, 5, 7, 9] 형태로 나오게 toString
    @Override
    public String toString() {
        //String은 값이 변경될때마다 새 객체를 생성한다
        //StringBuilder는 값 변경때마다가 새 String을 만드는 과정을 줄일 수 있다
        StringBuilder sb = new StringBuilder();
        Node<E> currentNode = firstNode;
        sb.append('[');
        for(int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");
            sb.append(currentNode.item.toString());
            currentNode = currentNode.next;
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main (String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();

        // LinkedList의 add: O(1)
        list.add(1);            // [1]
        list.add(2);            // [1, 2]
        list.add(3);            // [1, 2, 3]

        // LinkedList의 특정 위치값에 대한 add: O(N)
        list.insert(0, 4);      // [4, 1, 2, 3]
        list.insert(3, 5);      // [4, 1, 2, 5, 3]

        // LinkedList의 특정 위치값에 대한 set: O(N)
        list.set(2, -1);        // [4, 1, -1, 5, 3]
        System.out.println(list);

        // LinkedList.java는 ListIterator를 사용해 순차 탐색을 지원하지만
        // 이 클래스는 Node 접근자를 제공하여 직접 조작하는 형태로 사용합니다.
        // ListIterator와는 달리 실제 Node를 가리킵니다.
        Node<Integer> currentNode = list.getFirstNode();

        // 2칸 뒤 Node로 이동 후 현재 노드 정보를 출력하는 예제입니다.
        int currentIndex = 0;   // index: 0, value: 4
        for (int i = 0; i < 2; i++) {
            currentNode = currentNode.next;
            currentIndex++;
        }
        // index: 2, value: -1
        System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);

        // LinkedList의 특정 위치값에 대한 get: O(N)
        System.out.printf("index: %d, value: %d\n", 4, list.get(4));

        // LinkedList의 순차 접근 중 특정 노드에 대한 remove: O(1)
        list.removeNext(currentNode);
        System.out.println(list);   // [4, 1, -1, 3]

        // LinkedList의 특정 위치값에 대한 remove: O(N)
        list.remove(3);             // [4, 1, -1];
        int size = list.size();     // 3
        System.out.printf("Size: %d, %s", size, list);
    }
}