링크드 리스트 (Linked List) - 1

링크드 리스트 (Linked List)

연결구조 리스트
떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터구조

 

알아야 할 용어

• 노드 (Node) : 데이터 저장 단위 (포인터) 로 구성
• 포인터 (Pointer) : 하나의 노드에서 다음/이전 노드의 연결 정보를 가지고 있는 공간

링크드 리스트 형태

Singly-linked-list - Linked list - Wikipedia (일반 추가)

CPT-LinkedLists-addingnode - Linked list - Wikipedia (중간 추가)

CPT-LinkedLists-deletingnode - Linked list - Wikipedia (삭제)

 

 

링크드 리스트 장/단점

• 배열과 다르게 미리 공간 할당을 하지 않아도 됨
• 연결정보를 담는 공간이 필요, 저장공간 효율이 높지 않음
• 접근 속도가 느림
• 중간 데이터 삭제 시 앞뒤 연결을 재구성 해야함

 

링크드 리스트 구현 (한번쯤은 코드 작성하면서 이해하기)

public class SingleLinkedList<T> {
	puclic Node<T> head = null;
    
    public class Node<T> {
        T data;
        Node<T> next = null;
        
        public Node(T data) {
            this.data = data;
        }
    }
    
    /*
    * 노드 추가
    */
    public void add(T data) {
    	// head 가 null 이면 data를 넣어줌
    	if(this.head == null) {
            this.head = new Node<T>(data);
            
        // head 가 있다면
        } else {
            Node<T> node = this.head;
            
            // 해당 노드의 next가 null 이 아닐 경우에 실행
            while(node.next != null) {
            	node = node.next;
            }
            
            // 해당 노드의 next 가 null 이면 노드 추가
            node.next = new Node<T>(data);
        }
    }
    
    /*
    * 링크드 리스트 출력
    */
    public void getLinkedList() {
        if(head != null) {
            // head 부터 출력
            Node<T> node = this.head;
            System.out.print(node.data + " ");
            
            while(node.next != null) {
                node = node.next;
                System.out.print(node.data + " ");
            }
            
            System.out.println();
        }
    }
    
    /*
    * 노드 찾기
    */
    public Node<T> search(T searchData) {
        if(this.head == null) {
            return null;
            
        } else {
            Node<T> node = this.head;
            while(node != null) {
                if(node.data == searchData) {
                    return node;
                } else {
                    node = node.next;
                }
            }
            
            return null;
        }
    }
    
    /*
    * 노드 중간 추가
    */
    public voide midAdd(T data, T midAddData) {
        // 노드 찾기
        Node<T> searchNode = this.search(data);
        
        if(searchNode == null) {
            this.midAdd(midAddData);
            
        } else {
            // next 노드 선언
            Node<T> nextNode = searchNode.next;
            
            // 찾은 노드의 next를 추가할 노드로 연결
            searchNode.next = new Node<T>(midAddData);
            
            // 추가한 노드의 next를 next 노드로 연결
            searchNode.next.next = nextNode;
        }
    }
    
    /*
    * 노드 삭제
    */
    public boolean delNode(T delData) {
        if(this.head == null) {
            return false;
            
        } else {
            Node<T> node = this.head;
            
            // head 값이 삭제할 노드라면
            if(node.data == delData) {
                this.head = this.head.next;
                return true;
                
            } else {
                while(node.next != null) {
                    if(node.next.data == delData) {
                        node.next = node.next.next;
                        return true;
                    }
                    node = node.next;
                }
                
                return false;
            }
        }
    }
}


SingleLinkedList<Integer> linkedList = new SingleLinkedList<>();

// 추가
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.getLinkedList();	// 1 2 3

// 중간 추가
linkedList.midAdd(1, 5);    // 1 뒤에 5 넣기
linkedList.getLinkedList();    // 1 5 2 3

// 삭제
linkedList.delNode(5);
linkedList.getLinkedList();    // 1 2 3
linkedList.delNode(1);
linkedList.getLinkedList();    // 2 3
linkedList.delNode(6);		// false

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스