[Java 자료구조] 연결 리스트 구현해보기

연결 리스트(linked-list) 구현해보기

연결 리스트의 연산 중 노드를 추가하고, 제거하여 꺼내보는 addElement(), removeElement() 메서드와 중간에 노드를 삽입하는 insertElement() 메서드를 구현해본다. 헤드는 첫번째 노드를 가리키는 더미 노드 또는 헤드 자체가 첫번째 노드가 될 수 있는데, 후자의 경우로 구현한다.

 

먼저 removeElement()를 구현하기 위해서는 제거할 노드의 전 노드가 다음 노드를 가리키게 함으로써 구현할 수 있다. 

 

insertElement()의 경우 추가할 위치의 전 노드의 링크를 추가할 노드로 연결해야 하고 추가할 노드의 링크는 전 노드의 링크로 연결해야 한다.

 

결국 중간 요소를 변경하는 두가지 연산 모두 previous node(전 노드)를 찾는 연산이 필요하다.

 

MyListNode.java

• 노드를 구현한 클래스이다.
• 생성자는 default, data가 매개변수로 들어오는 경우, data에 link까지 지정하는 경우가 있다.

package ch03;

public class MyListNode {

	private String data;       // 자료
	public MyListNode next;    // 다음 노드를 가리키는 링크
	
	public MyListNode(){
		data = null;
		next = null;
	}
	
	public MyListNode(String data){
		this.data = data;
		this.next = null;
	}
	
	public MyListNode(String data, MyListNode link){
		this.data = data;
		this.next = link;
	}
	
	public String getData(){
		return data;
	}
}

 

addElement()

• 요소를 맨 뒤에 추가하는 메서드이다.
• 추가하려는 linked list에 요소가 없을 경우 노드를 생성하고 head로 설정한다.
• 맨 뒤에 있는 요소가 가리키는 link는 null이다.
• 새로운 노드를 만들고 head부터 마지막 요소를 찾아 뒤에 노드를 추가한다.
• 추가하고 난 뒤 count 변수를 증가시킨다.

public MyListNode addElement( String data )
{
    MyListNode newNode;

    if(head == null) {	// 첫 node일 경우
        newNode = new MyListNode(data);
        head = newNode;
    }

    else {
        newNode = new MyListNode(data);
        MyListNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    count++;

    return newNode;
}

 

insertElement()

• 원하는 위치에 요소를 추가하는 메서드이다.
• 지정한 위치가 범위를 벗어난 경우 오류를 반환한다.
• head에 추가할 경우 새로운 노드를 head로 설정하고 head를 가리키도록 한다.
• 중간에 요소를 추가할 경우 for문에서 preNode를 찾는다.
• 새로운 노드의 링크는 preNode가 가지고 있던 링크를 대입한다.
• preNode의 링크는 새로운 노드를 가리키도록 한다.

public MyListNode insertElement(int position, String data )
{
    int i;
    MyListNode tempNode = head;
    MyListNode preNode = null;

    MyListNode newNode = new MyListNode(data);

    if(position < 0 || position > count) {	// 오류 반환
        return null;
    }

    else if( position == 0 ) {	// head에 추가할 경우
        newNode.next = head;
        head = newNode;
    }

    else {	// 중간에 추가할 경우
        for (i = 0 ; i < position ; i++) {	// preNode를 찾음
            preNode = tempNode;
            tempNode = tempNode.next;
        }

        newNode.next = preNode.next;
        preNode.next = newNode;

    }

    count++;
    return newNode;		

}

 

removeElement()

• 지정 위치의 요소를 제거하는 메서드이다.
• head를 제거할 경우 head의 다음 요소를 head로 설정한다.
• preNode를 찾아 링크를 제거하려는 노드의 링크를 대입한다.
• count 변수를 감소시킨다.

public MyListNode removeElement(int position)
{
    MyListNode preNode = null;
    MyListNode tempNode = head;

    if (position < 0 || position > count) {
        return null;
    }

    else if (position == 0) {
        head = head.next;
    }

    else {
        for(int i = 0 ; i < position ; i++ ) {
            preNode = tempNode;
            tempNode = tempNode.next;
        }
        preNode.next = tempNode.next;

    }
    count--;
    return tempNode;
}

 

MyLinkedListTest.java

public class MyLinkedListTest {

	public static void main(String[] args) {
		
		MyLinkedList list = new MyLinkedList();
		
		list.addElement("A");
		list.addElement("B");
		list.addElement("C");
		list.printAll();
		
		list.insertElement(0, "A-1");
		list.insertElement(2, "B-1");
		list.printAll();
		
		list.removeElement(0);
		list.removeElement(1);
		list.printAll();
	}

}

 

수행 결과

A->B->C
A-1->A->B-1->B->C
A->B->C