자바 Singly LinkedList 구현

linkedlist는 링크로 서로를 연결하는 List이다. 그중에서 단일 연결 링크드 리스트를 구현해 보겠다.

이렇게 서로 연결되어있다.

다시말하지만 중복을 허용하고 저장순서가 유지된다.
추가할 때 어디서 추가할것이라고 말을 하지 않으면 뒤에 append한다.

Node class

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

    Node(E data){
        this.data = data;
        this.next = null;
    }
}

같은 패키지에 Node 클래스를만든다.

Singly LinkedList 구현

• 클래스 및 생성자 구성
• search 메소드 구현
• add 메소드 구현
• get, set, indexOf, contains 메소드 구현
• remove 메소드 구현
• size, isEmpty, clear 메소드 구현

클래스 및 생성자 구성

public class SLinkedList<E> implements List<E>{
	public MySLinkedList(){
        head = null;
        tail = null;
        size = 0;
    }
}
  

head와 tail에 null값을 넣어주고 size는 0으로 만든다.

search 메소드 구현

public Node<E> search(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }

        Node<E> x = head;

        for(int i = 0; i < index; i++){
            x = x.next;
        }

        return x;
    }

index에 위치의 Node를 반환한다.
무엇을 반환하는지 헷갈리지 말것

add 메소드 구현

add에는 크게 3가지 방법이 있다.
처음에 추가, 중간에 추가, 마지막에 추가이다.

    public void addFirst(E element){
        Node<E> new_Node = new Node<>(element);

        new_Node.next = head;
        head = new_Node;

        if(size == 0){
            tail = head;
        }

        size++;
    }
    public void addLast(E element){
        Node<E> new_Node = new Node<>(element);

        if(size == 0){
            addFirst(element);
            return;
        }

        tail.next = new_Node;
        tail = new_Node;

        size++;
    }

첫번째에 넣기, 마지막에 넣기이다. 그리고 신경써야 하는것은 size== 0일때 이다.

@Override
    public void add(int index, E element) {
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException();
        }

        if(size == 0){
            addFirst(element);
            return;
        }

        if(index == size){
            addLast(element);
            return;
        }
        Node<E> new_Node = new Node<>(element);

        Node<E> prev_node = search(index - 1);

        new_Node.next = prev_node.next;
        prev_node.next = new_Node;
        size++;

    }

중간에 추가하는 코드이다.

get, set, indexOf, contains 메소드 구현

@Override
    public E get(int index) {
        return search(index).data;
    }
    
    @Override
    public E set(int index, E value) {
        Node<E> search = search(index);
        E data = search.data;
        search.data = value;

        return data;
    }
     @Override
    public int indexOf(Object o) {
        if (size < 0){
            throw new IndexOutOfBoundsException();
        }
        int index = 0;
        for(Node<E> x = head; x.next != null; x = x.next){
            if(o.equals(x.data)){
                return index;
            }
            index++;
        }
        
        return -1;
    }
    @Override
    public boolean contains(Object value) {
        return indexOf(value) > -1;
    }
    

remove 메소드 구현

remove도 생각해야할게 있다.

public E remove(){
        if(size  < 0){
            throw new IndexOutOfBoundsException();
        }
        E data = head.data;

        head = head.next;
        size--;

        if(size == 0 ){
            tail = null;
        }

        return data;

    }

    @Override
    public E remove(int index) {
        if(index == 0){
            return remove();
        }

        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> prev_node = search(index - 1);

        Node<E> remove_node = prev_node.next;

        prev_node.next = remove_node.next;

        if(prev_node.next == null) {
            tail = prev_node;
        }
        size--;

        return remove_node.data;
    }

    @Override
    public boolean remove(Object value) {
        int index = indexOf(value);
        if(index >= 0){
            remove(index);
        }

        return false;

    }

remove() 첫번째 요소 삭제
remove(int index) index에 위치한 요소 삭제
remove(Object o) o Object 삭제

size, isEmpty, clear 메소드 구현

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

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

https://github.com/Hodu-moon/DataStructure/tree/master/java/_02_LinkedList