[자료구조] 연결 리스트 (Linked List)

1. 연결 리스트 (Linked List)

• 데이터를 링크로 연결해서 관리하는 자료구조
• 자료의 순서는 정해져 있지만, 메모리상의 연속성은 보장되지 않음
• 장점
  • 데이터 공간을 미리 할당할 필요 없음
  • 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이
• 단점
  • 연결구조를 위한 별도 데이터 공간 필요
  • 연결 정보를 찾는 시간 필요 (접근 속도가 상대적으로 느림)
  • 데이터 추가/삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요

2. 연결 리스트 기본 구조

• 노드(Node)
  • 데이터 저장 단위로 값과 포인터로 구성
    • 포인터(Pointer) : 다음 노드나 이전 노드의 연결 정보

3. 연결 리스트 기본 연산

• 데이터 추가
  • 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요
  • head에 데이터 추가
    • 추가할 데이터를 담을 노드 생성
    • 링크 연결 작업
    • head 이전 작업
      

      

      가장 앞에 데이터 추가

    • tail에 데이터 추가
      • 추가할 데이터를 담을 노드 생성
      • head로부터 끝 노드까지 순회
      • 링크 연결 작업
        

        

        가장 끝에 데이터 추가

    • 중간에 데이터 추가
      • 추가할 데이터를 담을 노드 생성
      • head로부터 데이터 추가 위치 직전 노드까지 순회
      • 링크 연결 작업
        

        

        중간에 데이터 추가

• 데이터 삭제
  • 데이터 삭제 위치(head, 중간, tail)에 따른 연결 작업 필요
  • head 데이터 삭제
    • 삭제 대상 노드 지정 (delete_node)
    • head 이전 작업
    • delete_node 삭제
      

      

      가장 앞의 데이터 삭제

  • tail 데이터 삭제
    • head로부터 가장 끝까지 순회
    • 끝 노드 삭제
    • 삭제 이전 노드의 링크 처리
      

      

      가장 끝의 데이터 삭제

  • 중간 데이터 삭제
    • head로부터 삭제 대상 노드까지 순회 및 해당 노드 지정 (delete_node)
    • 삭제 대상 이전/이후 노드의 링크 연결 작업
    • delete_node 삭제
      

      

      중간 데이터 삭제

4. 코드

• 끝에 데이터 추가/삭제

Class Node {
    int data;
    Node next;
    
    Node() {}
    Node(int data, Node next) {
    	this.data = data;
        this.next = next;
    }
}

Class LinkedList {
    Node head;
    
    LinkedList() {}
    LinkdeList(Node node) {
    	this.head = node;
    }
    
    // 연결 리스트 비어있는지 확인
    public boolean isEmpty() {
    	if(this.head == null) {
            return true;
        }
        return false;
    }
    
    // 연결 리스트의 맨 뒤에 데이터 추가
    public void addData(int data) {
    	if(this.head == null) {
            this.head = new Node(data, null);
        } else {
            Node cur = this.head;
            while(cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(data, null);
        }
    }
    
    // 연결 리스트의 맨 뒤에 데이터 삭제
    public void removeData() {
    	if(this.isEmpty()) {
            System.out.println("List is Empty");
            return;
        }
        
        Node cur = this.head;
        Node prev = cur;
        
        while(cur.next != null) {
            prev = cur;
            cur = cur.next;
        }
        
        if(cur == this.head) {
            this.head = null;
        } else {
            prev.next = null;
        }
    }
    // 연결 리스트에서 데이터 찾기
    public void findData(int data) {
    	if(this.isEmpty()) {
       	    System.out.println("List is Empty");
            return;
        }
        
        Node cur = this.head;
        while(cur != null) {
            if(cur.data == data) {
                System.out.println("Data exist");
                return;
            }
            cur = cur.next;
        }
        System.out.println("Data not found");
    }
    
    // 연결 리스트의 모든 데이터 출력
    public void showData() {
        if(this.isEmpty()) {
            System.out.println("List is Empty");
            return;
        }
        
        Node cur = this.head;
        while(cur != null) {
            System.out.println(cur.data + " ");
            cur = cur.data;
        }
        System.out.println();
    }
}

끝에 데이터 추가/삭제 동작 과정

• 중간에 데이터 추가/삭제

class LinkedList2 extends LinkedList {
	LinkedList2(Node node) {
    	this.head = node;
    }
    
    // 연결 리스트 중간에 데이터 추가
    // before_data가 null인 경우, 가장 뒤에 추가
    // before_data에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
    public void addData(int data, Integer beforeData) {
        if(this.head == null) {
            this.head = new Node(data, null);
        } else if(beforeData == null) {
        	Node cur = this.head;
            while(cur.next != null) {
            	cur = cur.next;
            }
            cur.next = new Node(data, null);
        } else {
            Node cur = this.head;
            Node prev = curl
            while(cur != null) {
                if(cur.data == beforeData) {
                    if(cur == this.head) {
                        this.head = new Node(data, this.head);
                    } else {
                        prev.next = new Node(data, cur);
                    }
                    break;
                }
                prev = cur;
                cur = cur.next;
            }
        }
    }
    
    // 연결 리스트 중간 데이터 삭제
    public void removeData(int data) {
        if(this.isEmpty()) {
            System.out.println("List is Empty");
            return;
        }
        
        Node cur = this.head;
        Node prev = cur;
        
        while(cur != null) {
            if(cur.data == data) {
                if(cur == this.head) {
                    this.head = cur.next;
                } else {
                    prev.next = cur.next;
                }
                break;
            }
            prev = cur;
            cur = cur.next;
        }
    }
}