리스트 (List) - 연결리스트(LinkedList)

배열과 다르게 불연속적인 메모리 공간을 지니며 각각의 데이터 요소들을 포인터로 가리킴으로써 순서를 유지한다. 

때문에 삽입/삭제에 유리하며 메모리의 재사용이 편리하다.

반면에 검색 성능이 좋지 않고, 다음 요소를 가리키는 포인터가 차지하는 추가적인 메모리가 필요하다.

 

리스트의 구조

LinkedList (연결 리스트)

물리적으로 흩어져 있는 데이터(노드)를 포인터를 사용하여 서로 연결하여 하나로 묶음

 

노드의 구조

노드는 데이터를 저장하는 데이터 필드와 다른 노드를 가리키는 링크로 구성되어 있다.

 

 

연결 리스트의 구현

1. 노드 클래스 구현

class ListNode{
    private String data;	// 노드가 지니는 Data
    public ListNode link;	// 다음 노드를 가리키는 참조변수
    
    
	//매개변수로 노드에 저장할 데이터를 받은 생성자
    public ListNode(String data) {	
        this.data = data;	// 해당 값으로 노드 객체에 저장
        this.link = null;	// 다음 노드는 없음으로 null
    }

	// 노드의 데이터를 출력하는 메서드
    public String getData() {	
        return this.data;
    }
}

 

2. 연결 리스트 클래스 구현

class LinkedList {
    private ListNode head;	// head 노드

    public LinkedList() {	// 연결리스트 기본 생성자
        head = null;
    }
    
    public void insertNode(String data) {...}	 //노드 삽입 메서드
    public void deleteNode(String data) {...}	//노드 삭제 메서드
    
}

 

3. 노드 삽입 메서드 구현

public void insertNode(String data) {
	ListNode newNode = new ListNode(data);	//입력받은 데이터를 가진 노드 객체 생성
  
	if (head == null) {  // 연결 리스트의 헤더 노드가 없다면 
		this.head = newNode; // 현재 삽입하는 노드가 헤더 노드가 됨으로 연결리스의 헤더에 대입
    } else { // 연결 리스트의 헤더 노드가 존재한다면
    	ListNode tempNode = head;	
        // 헤더 노드의 다음 노드들을 통해 마지막 노드에 접근하기 위해 임시 노드에 헤더를 대입한다
        
        while (tempNode.link != null) {	// 다음 노드가 없을때 까지 반복
            tempNode = tempNode.link;	//다음 노드를 현재 노드로 대입
        }
        // 즉, 연결 리스트의 마지막 노드를 찾아 tempNode에 대입한다
        
        tempNode.link = newNode;	
        // 연결 리스트의 마지막 노드가 다음 노드로 새로 입력받은 노드를 가리키도록 함
    }
}

 

4. 노드 삭제 메서드 구현

public void deleteNode(String data) {
	ListNode preNode = head;	// 연결 리스트의 헤더 노드를 preNode에 대입
    ListNode tempNode = head.link;	// 연결 리스트의 헤더 노드가 가리키는 다음 노드를 tempNode에 대입

	// 만약 삭제 하려는 데이터와 헤더 노드의 데이터가 같다면
    if (data.equals(preNode.getData())) {	
    	// 헤더 노드의 다음 노드를 헤더로 변경하고
        head = preNode.link;	
        
        // 기존 헤더 노드가 가리키는 다음 노드를 null로 하여 기존의 헤더 노드의 다음 노드와의 연결을 끊는다 
        preNode.link = null;	
        
   }
   
   // 만약 삭제 하려는 데이터와 헤더 노드의 데이터가 같지 않다면
   else {
   		// 헤더 노드가 가리키는 다음 노드의 값이 null일때 까지 밑의 코드 블럭을 반복
        // (즉, 연결 리스트의 각 요소들에 접근)
   		while (tempNode != null) {
        
			// 만약 삭제하려는 데이터와 현재 노드의 데이터가 같다면
        	if (data.equals(tempNode.getData())) {	
            
            	// 만약 다음 노드가 null 이라면(현재 노드가 마지막 노드라면)
            	if (tempNode.link == null) {
                	
                    // 현재 노드를 null로 변경하여 이전 노드와의 연결을 끊는다
                	preNode.link = null;	
                    
                } else {	// 만약 다음 노드가 null이 아니라면(존재한다면)
                	preNode.link = tempNode.link;	// 이전의 노드가 다음 노드를 가리키게함
                    tempNode.link = null;	// 현재 노드가 가리키는 값을 null로 하여 연결을 끊음
                } break;	
            } else {
            	preNode = tempNode;	// 현재 노드를 이전 노드로 변경
                tempNode = tempNode.link;	// 다음 노드를 현재 노드로 변경 
           }
        }
    }
}

 

5. 노드 검색 메서드

public ListNode searchNode(String data) {
	ListNode tempNode = this.head;
    while (tempNode != null) {
    	if (data.equals(tempNode.getData())) {
        	return tempNode;
        } else {
            tempNode = tempNode.link;
        }
    }
 	return tempNode;
}