1. 리스트(2) Linked list

• 연결 Link (노드)
  데이터 item(내가 원하는 값) 와 포인터 pointer(다른 노드를 가르킴) 로 구성된다.

        리스트를 연결을 이용해 표현하는 방법은?

• Link 연결 구현

class Link<E>{
    private Link<E> next;
    private E item;
    
    public Link(E item, Link<E> next){
        this.item = item;
        this.next = next;
    }
    
    E item(){return item;}
    E setItem(E item){return this.item;}
    
    Link<E> next(){return next;}
    Link<E> setNext(Link<E> next){return this.next;}
    
}

• 연결리스트를 구현할 때 head 부분을 따로 둬야할까?
  A> 따로 두는게 좋다.
  head 가 null일 경우가 있기 때문에, head가 null인지 아닌지에 대한 여부를 계속 검사해야하는 if else구문을 줄이기 위해 따로 head를 두는게 더 효율적인 경우가 많다.

• 연결리스트 Linked List 구현( 주석에 적힌 작동원리를 꼭 이해하자.)

public class LinkedList<E> implements List<E> {

    Link<E> head, tail;
    int size;

    public LinkedList() {
        head = new Link<E>(null, null);
        tail = head; // head, tail이 처음엔 같이 있음
        size = 0;
    }

    @Override
    public void clear() {
        // tail을 다시 head에 붙이면 나머지가 날라갈 것
        tail = head;
        head.next = null;
        size = 0;
    }

    @Override
    public void insert(int pos, E item) {
        // 넣고자 하는 노드를 만들고, 만든 노드의 링크를 연결해주고 전 노드와 연결하는 순서
        // 1. curr을 직전의 노드까지 이동하기
        Link<E> curr = head;
        for (int i = 0; i < pos; i++)
            curr = curr.next;
        // 2. curr.next와 연결되는 새로운 노드를 먼저 만들고(new Link<E>(item, curr,next);
        // 3. 이렇게 만든 새로운 노드를 curr과 연결을 시키면 됨(curr.next = 노드);
        curr.next = new Link<E>(item, curr.next);
        size++;
    }

    @Override
    public void append(E item) {
        // tail이 가리키고 있는 next값을 연결해주고 tail을 바꿔줌
        tail.next = new Link<E>(item, null);
        tail = tail.next;
        size++;
    }

    @Override
    public void update(int pos, E item) {
        // head가 비어있으므로 인덱스 값 + 1의 next를 해주면 대상 값을 바꿀 수 있음
        Link<E> curr = head;
        for (int i = 0; i < pos; i++)
            curr = curr.next;
        curr.next.item = item;
    }

    @Override
    public E getValue(int pos) {
        // 원하는 곳까지 이동해서 값 가져오기
        Link<E> curr = head;
        for (int i = 0; i < pos; i++)
            curr = curr.next;

        return curr.next.item;
    }

    @Override
    public E remove(int pos) {
        // 바로 전 노드의 링크를 next.next로 연결해버리면 됨(연결 끊기)
        Link<E> curr = head;
        for (int i = 0; i < pos; i++)
            curr = curr.next;

        // curr.next = curr.next.next; tail을 지우고자 할때 문제가 생김.
        // tail이 가르키는게 여전히 tail임
        if (curr.next == tail)
            tail = curr;

        E ret = curr.next.item;

        curr.next = curr.next.next;
        size--;
        return ret;
    }

    @Override
    public int length() {
        return size;
    }

}

• insert의 작동 원리

• remove의 작동 원리