[Java][알고리즘] LinkedList

자료들을 반드시 연속적으로 배열시키지 않고 링크(link)를 통해 리스트를 형성

노드(node)는 데이터를 담는 그릇, 링크(link)는 리스트의 순서를 유지할 수 있게 해주는 연결고리의 구조를 가지고있다

스택, 큐, 해시 등의 기본이 됨

 

장점

• 삽입, 삭제 작업이 용이하다
• 기억공간이 연속적이지 않아도 저장이 가능하다.
• 메모리를 효율적으로 사용
• 데이터 재구성 용이
• 대용량 데이터를 처리하는데 적합

단점

• 접근속도가 느리다.(포인터를 찾아가는 시간이 필요하기 때문에 배열에 비해 접근속도가 느림)
• 중간 노드의 연결이 끊어지면 그 다음 노드를 찾기 힘들다.
• 구성 및 사용방법이 까다로움

배열 vs 링크드리스트 데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이뤄질 경우는 배열이 유리함. 반면 데이터의 삽입/삭제가 빈번하게 이뤄질 경우에는 연결리스트가 유리.

 

ListNode

ListNode 는 다음 노드를 가리키는 포인터만 존재하므로 data 와 next 를 가진다.

public class ListNode {
	private int data;
    private ListNode next;
    
    ListNode(int data) {
    	this.data = data;
    }
    
    public int getData() {
		return this.data;
	}

	public ListNode getNext() {
		return this.next;
	}

	public void setNext(ListNode nextNode) {
		this.next = nextNode;
	}
}

LinkedList

public class LinkedList {
	private ListNode head; // 현재리스트 노드
	private int size;

	LinkedList() {
		this.head = null;
		this.size = 0;
	}
    
    public ListNode add(ListNode nodeToAdd, int position) {
    	this.size++;
        
        // position 유효성 체크
        if(validatePositionRange(position)) {
        	return null;
        }
        
        // 해당 위치 찾기
        ListNode pre = null, cur = this.head;
        while(--position > 0) {
        	pre = cur;
            cur = cur.getNext();
        }	
        
        // 삽입 위치가 맨 앞인 경우
        if(pre == null) {
        	nodeToAdd.setNext(cur);
            this.head = nodeToAdd;
            return this.head;
        }
        
        // 그 이외에 경우
        pre.setNext(nodeToAdd);
        nodeToAdd.setNext(cur);
        return nodeToAdd;
    }
    
    public ListNode remove(int positionToRemove) {
        // positionToRemove 유효성 체크
        if(validatePositionRange(positionToRemove)) {
            return null;
        }

        // 해당 위치 찾기
        ListNode pre = null, cur = this.head;
        while(--positionToRemove > 0) {
            pre = cur;
            cur = cur.getNext();
        }

        // 연결 리스트의 크기 감소
        this.size--;

        // 삭제 위치가 맨 앞일 경우
        if(pre == null) {
            this.head = cur.getNext();
            return cur;
        }

        // 그 이외의 경우
        pre.setNext(cur.getNext());
        return cur;
	}
	
    public boolean contains(ListNode nodeToCheck) {
        // 순회
        ListNode cur = this.head;
        while(cur != null) {
            // 같은 ListNode라면
            if(cur == nodeToCheck) {
                return true;
            }
            cur = cur.getNext();
        }
        // 끝까지 체크하고도 같은 ListNode가 없다면
        return false;
    }
    
}