자료구조 시작 전 사전지식_linkedList

linkedList

• Collection 프레임워크의 일부분
• java.util 패키지에 소속되어 있다.
• 모든 데이터가 데이터와 주소를 별도로 가지고 있어, 포인터와 주소를 사용해 연결한다.
• 각 데이터는 노드라고 불리고 ArrayList보다 선호된다.
• ArrayList보다 검색에 있어서 느리다는 단점이 있다.

 

* 이해를 돕기 위해 linkedlist를 구현했습니다.

class LinkedList {
    private ListNode head;
    
    public LinkedList() {
        head = null;
    }
    
    // 중간에 데이터 삽입
    public void insertMiddleNode(ListNode preNode, String data) {
        // listNode 객체 생성
        ListNode newNode = new ListNode(data);
        // preNode에 연결되어있던 다음 데이터를 newNode에 연결
        newNode.link = preNode.link;
        // preNode에 newNode를 연결
        preNode.link = newNode;
    }
    
    // 마지막에 데이터 삽입
    public void insertLastNode(String data) {
        // listNode 객체 생성
        ListNode newNode = new ListNode(data);
        
        if (head == null) {
            // head가 비어있으면 첫번째인 head에 데이터 삽입
            this.head = newNode;
        } else {
            // head가 존재하면 반복문을 수행하며 마지막 노드를 찾기
            ListNode tempNode = head;
            while (tempNode.link != null) {
                // 마지막 노드라면 link가 비어있기 때문에 "tempNode.link != null" 조건을 만족할 때까지 수행
                tempNode = tempNode.link;
            }
            // 마지막 노드에 newNode를 삽입
            tempNode.link = newNode;
        }
    }
    
    // 마지막 노드 삭제
    public void deleteLastNode() {
        ListNode preNode;
        ListNode tempNode;
        
        // head가 비어있다면 데이터가 없는 것이기 때문에 추가로 로직 수행 하지 않는다.
        if (head == null) {
            return;
        }
        
        if (head.link == null) {
            // head.link가 비어있다면 전체 데이터는 head 하나만 존재하기 때문에 head만 삭제
            head = null;
        } else {
            // head.link가 존재한다면 마지막 노드를 찾기 위해 head데이터와 head.link를 임시 변수에 담아 마지막 노드를 찾음
            preNode = head;
            tempNode = head.link;
            
            // 마지막 노드를 찾을때까지 반복문 수행
            while(tempNode.link != null) {
                preNode = tempNode;
                tempNode = tempNode.link;
            }
            
            // 마지막 노드의 link를 삭제해주면서 연결을 끊어준다.
            preNode.link = null;
        }
    }
    
    // 중간 노드 삭제
    public void deleteMiddleNode(String data) {
        ListNode preNode = head;
        ListNode tempNode = head.link;
        
        if (data.equals(preNode.getData())) {
            // data가 head의 값과 같다면 head.link를 null처리하면서 노드를 삭제해준다.
            head = preNode.link;
            preNode.link = null;
        } else {
            while(tempNode != null) {
                if(data.equals(tempNode.getData())) {
                    // tempNode의 값과 같다면 마지막 데이터인지 확인 후 데이터 삭제
                    if(tempNode.link == null) {
                        // 마지막 데이터라면 이전 데이터와의 연결을 끊어주면서 삭제 후 반복문 종료
                        preNode.link = null;
                    } else {
                        // 마지막 데이터가 아니라면 tempNode와 연결되어있던 데이터를 preNode에 연결해주면서 삭제 후 반복문 종료
                        preNode.link = tempNode.link;
                        tempNode.link = null;
                    }
                    break;
                } else {
                    // tempNode와 데이터가 다르다면 다음 데이터로 이동하며 반복문 수행
                    preNode = tempNode;
                    tempNode = tempNode.link;
                }
            }
        }
    }
    
    // 해당 노드 찾기
    public ListNode searchNode(String data) {
        ListNode tempNode = this.head;
        
        // tempNode가 null아 아닐때까지 반복문을 수행
        while(tempNode != null) {
            if (data == tempNode.getData()) {
                // tempNode가 찾는 data라면 바로 반환
                return tempNode;
            } else {
                // tempNode가 찾는 data가 아니라면 다음 데이터로 이동하며 반복문 수행
                tempNode = tempNode.link;
            }
        }
        return tempNode;
    }
    
    // linkedlist에 있는 데이터를 역순으로 정렬
    public void reverseList() {
        ListNode nextNode = head;
        ListNode currentNode = null;
        ListNode preNode = null;
        
        while(nextNode != null) {
            // 새로 선언한 변수에 head부터 차례로 넣어준다.
            preNode = currentNode;
            currentNode = nextNode;
            nextNode = nextNode.link;
            currentNode.link = preNode;
        }
        // 정렬한 노드를 head로 초기화시켜준다.
        head = currentNode;
    }
    
    // linkedlist를 출력해준다.
	public void printList(){
		ListNode temp = this.head;
		System.out.printf("L = (");
		while(temp != null){
		    // 끝까지 반복문을 수행하면서 print해준다.
			System.out.printf(temp.getData());
			temp = temp.link;
			if(temp != null){
				System.out.printf(", ");
			}			
		}
		System.out.println(")");
	}
    
}

class ListNode {
    private String data;
    public ListNode link;
    
    public ListNode() {
        this.data = null;
        this.link = null;
    }
    public ListNode(String data) {
        this.data = data;
        this.link = null;
    }
    public ListNode(String data, ListNode link) {
        this.data = data;
        this.link = link;
    }
    public String getData() {
        return this.data;
    }
}



public class Main {
	public static void main(String[] args) {
        LinkedList L = new LinkedList();
		
		System.out.println("(1) 공백 리스트에 노드 3개 삽입하기");
		L.insertLastNode("월");
		L.insertLastNode("수");
		L.insertLastNode("일");
		L.printList();	// L = (월, 수, 일)

		System.out.println("(2) 수 노드 뒤에 금 노드 삽입하기");
		ListNode pre = L.searchNode("수");
		if(pre == null) 
			System.out.println("검색실패>> 찾는 데이터가 없습니다.");
		else{
			L.insertMiddleNode(pre, "금");
			L.printList();	// L = (월, 수, 금, 일)
		}

		System.out.println("(3) 리스트의 노드를 역순으로 바꾸기");
		L.reverseList();
		L.printList();	// L = (일, 금, 수, 월)

		System.out.println("(4) 리스트의 마지막 노드 삭제하기");      
		L.deleteLastNode();
		L.printList();	// L = (일, 금, 수)
	}
}