JAVA 자료구조 (리스트) - LinkedList 3 (기타작업)

LinkedList

기타 작업

 

나머지 작업들을 하나씩 정리해보자. 리스트의 k번째 원소를 알려주는 함수 get(k)는 k번째 노드를 찾은 다음 그 노드의 원소를 리턴한다.

 

 

알고리즘 5-13 연결 리스트의 k번째 원소 알려주기

public T get(int k){
    return getNode(k).item;
}

 

k번째 노드를 찾는 함수 getNode(k)는 여러 함수에서 필요한 보조 작업으로 코드는 다음과 같다. 노드의 인덱스는 0 ~ numItems -1 사이에 있지만 더미 헤드를 찾는 경우에도 지원하기 위해 k = -1이면 더미 헤드를 찾는 것으로 해석한다. 첫 번째 노드는 0번째 노드로 표기하고, 더미 헤드 노드는 -1번째 노드로 표기한다.

public T getNode(int k){
    if(k >= -1 && k <= numItems-1){
    	currNode = head; // ◀ 더미 헤드
        for(int i = 0; i <=k ;i++){
          currNode = currNode.next
        }
        return currNode;
    }else return null;
}

 

 

 

알고리즘 5-14 연결 리스트의 k번째 원소를 x로 대체하기

public void set( int k, T x){
    if(k >= 0 && k <= numItems -1)
    	getNode(k).item = x;
    else
    	return null;
}

 

리스트의 k번째 원소를  원소 x로 대체하는 작업 set( k, x )의 핵심은 getNode(k).item = x 인데 범위를 벗어난 원소를 요구할 경우까지 감안하면 [알고리즘 5-14]와 같다.

 

 

알고리즘 5-15 원소x가 연결 리스트의 몇 번째 원소인지 알려주기

public int indexOf(T x){
    currNode = head // ◀ 더미 헤드
    for(int i = 0; i < numItems-1; i++){
    	currNode = currNode.next
        if(currNode.item == x) return i;
        return NOT_FOUND;
    }
}

 

원소 x가 리스트의 몇 번째 원소인지를 알아내는 알고리즘 indexOf(x)는 [알고리즘 5-15]와 같다.

 

 

알고리즘 5-16 기타 작업들

public int len(){    // ◀ 리스트의 총 원소 수 알려주기
    return numItems;
}

public boolean isEmpty(){	// ◀ 리스트가 비었는지 알려주는 메서드
	if(numItems == 0)
    	return true;
    else
    	return false;
}

public void clear(){	// ◀ 리스트 깨끗이 비우기
	newNode.next = null; // ◀ 더미 헤드 노드
    head = newNode;
    numItems = 0;
}

 

나머지 작업들은 비교적 단순 하므로 [알고리즘 5-16]에 모아서 정리하였다. 리스트의 총 원소수를 알려주는 len()은 변수 numItems의 값을 리턴하면 된다. 리스트가 비었는지 알려주는 isEmpty()은 numItems 값이 0인지 여부를 리턴하면 된다. 리스트를 깨끗이 청소하는 clear()는 변수 head가 null값을 갖는 대신 .next 값이 null인 더미 헤드 노드르 가리키게 하면 된다.

 

 

📒 객체 지향 언어의 철학 조금 느슨하게 풀기

 앞서 다룬 LinkedListd의 사용될 Node 객체의 구조는 다음과 같다.

객체 지향 언어의 철학을 엄격히 적용한다면 이 노드 구조는 권하지 않는 스타일이다. 객체의 필드에 대한 외부 접근은 꼭 필요한 것만 한다는 객체 지향 언어의 철학에 맞지 않기 때문이다. 이 철학을 충실하게 따르는 버전의 경우, 노드 객체에서 요구하는 작업은 다음과 같다.

• 노드에 원소를 저장한다.
• 노드의 원소를 알려준다.
• 노드의 링크 값을 할당한다.
• 노드의 링크 값을 알려준다.

 

위 그림은 노드 객체를 가장 교과서적으로 설계한 것이다. 노드에는 원소를 담는 필드인 item과 레퍼런스 링크를 담는 next가 있고 이들은 노드 객체의 바깥에서 직접 접근하지 못하도록 했다. 두 필드에 접근하려면 setItem(), getItem(), setNext(), getNext()함수를 거쳐서 접근해야 한다.

 

BestPracticesNode.java

public class BestPrecticesNode<T> {
    private T item;
    private BestPrecticesNode next;

    public BestPrecticesNode(T newItem) {
        this.item = newItem;
    }

    public BestPrecticesNode(T newItem, BestPrecticesNode nextNode) {
        this.item = newItem;
        this.next = nextNode;
    }

    public T getItem() {
        return item;
    }

    public void setItem(T newItem) {
        this.item = newItem;
    }

    public BestPrecticesNode getNext() {
        return next;
    }

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

 

 

위 코드와 같이 하는 것이 클래스 내부 보호 측면에서는 바람직하다. 하지만 앞으로 JAVA를 이용한 자료구조를 구현하는 게시물에서 매우 단순한 구조와 잡업에 대해 직접 접근하지 못하게 하는 것이 다소 어색하게 느껴지기 때문에 이 부분만 벽을 해제해 다음 코드에 오는 코드와 같은 구조로 Node객체를 구성하여 두 필드 item과 next를 외부에서 바로 접근할 수 있게 하고, 이들에게 접근하기 메서드 4개를 없앤다.

 

Node.java

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

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

 

 

메서드를 이용해서 item에 간접접근

Node a = new Node();
a.setItem(10);

 

그 결과 위 와 같이 노드를 생성하고 메서드를 통해 item에 접근하지 않고.

 

item필드에 직접접근

Node a = new Node();
a.item = 10;

위 코드와 같이 필드 item에 바로 접근하게 된다. 

 

 

 

[출처 - 쉽게 배우는 자료구조 with 자바,  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7033044159

IT CookBook, 쉽게 배우는 자료구조 with 자바