[Java] 리스트

[Java] 리스트

---

리스트(list)

• 기본적인 연산: 삽입, 삭제, 검색 등
• 리스트를 구현하는 대표적인 두가지 방법: 1) 배열, 2) 연결리스트

배열

• 크기가 고정 - reallocation 필요
• 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야함

연결리스트

• 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며 길이의 제한이 없음
• but, 랜덤 액세스 불가 ( 배열의 index로 접근하는 것을 의미 )

연결리스트의 노드

• 각각의 노드는 "데이터 필드"와 하나 혹은 그 이상의 "링크 필드"로 구성
  • single Linked - 단방향( 뒷 노드의 주소 ) / doubley linked - 양방향( 앞, 뒤 노드의 주소 )
• 링크 필드는 다음 노드를 참조
• 첫 번째 노드의 주소는 따로 저장되어야함

---

연결리스트 구현코드

 

Node.java

public class Node<T> {
    public T data;
    public Node<T> next;

    public Node(T item){
        this.data=item;
        this.next=null;
    }
}

MySingleLinkedList.java

public class MySingleLinkedList<T> {

    public Node<T> head;
    public int size = 0;

    public MySingleLinkedList(){
        head=null;
        size=0;
    }

    public void addFirst( T item ){
        Node<T> newNode = new Node<T>(item);
        newNode.next = head;
        head = newNode;
        size++;
    }

    public void addAfter(Node<T> before, T item) {
        Node<T> temp = new Node<T>(item);
        temp.next = before.next;
        before.next=temp;
        size++;
    }

    public T removeFirst() {
        if (head == null) {
            return null;
        }else{
            T temp=head.data;
            head = head.next;
            size--;
            return temp;
        }
    }

    public T removeAfter(Node<T> before){
        if(before.next==null){
            return null;
        }else{
            T temp=before.next.data;
            before.next=before.next.next;
            size--;
            return temp;
        }
    }

    public void add(int index, T item) {   // insert
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            addFirst(item);
        }else{
            Node<T> node = getNode(index-1);
            addAfter(node, item);
        }
    }

    public T remove(int index){       // delete
        if (index < 0 || index > size) {
            return null;
        }
        if (index == 0) {
            return removeFirst();
        }else{
            Node<T> prev = getNode(index-1);
            return removeAfter(prev);
        }
    }

    public T remove(T item) {
        Node<T> p=head;
        Node<T> q=null;
        while (p != null && p.data.equals(item)) {
            q = p;
            p = p.next;
        }
        if (p == null) {
            return null;
        }
        if (q == null) {
            return removeFirst();
        }else{
            return removeAfter(q);
        }
    }

    public Node<T> getNode(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node<T> p=head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    public T get(int index){
        if (index < 0 || index >= size) {
            return null;
        }
        return getNode(index).data;
    }

    public int indexOf(T item){          //search
        Node<T> p = head;
        int index = 0;
        while (p != null) {
            if (p.data.equals(item)) {
                return index;
            }
            p = p.next;
            index++;
        }
        return -1;
    }

    public static void main(String[] args) {

        MySingleLinkedList<String> list = new MySingleLinkedList<String>();
        list.addFirst("Monday");
        list.addFirst("Sunday");
        list.add(2, "Saturday");
        list.add(2, "Friday");
        list.remove("Friday");
        int index = list.indexOf("Saturday");
    }
}