연결 리스트(Linked List)

연결 리스트(Linked List)

• 데이터를 링크로 연결해서 관리하는 자료구조

• 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음 ↔ 배열(Array)는 이와 다르게 메모리상에서의 연속성이 보장됨

연결 리스트의 장점

• 데이터 공간을 미리 할당할 필요 없음.

• 즉, 리스트의 길이가 가변적이라 데이처 추가/삭제 용이

연결 리스트의 단점

• 연결구조를 위한 별도 데이터 공간 필요

• 연결 정보를 찾는 시간이 필요

• 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요

연결 리스트 기본 구조

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

연결 리스트 기본 연산

• 데이터 추가
• 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요

1. 추가할 데이터를 담은 노드 생성

2. 링크 연결 작업

3. head 이전 작업

1. 추가할 데이터를 담을 노드 생성

2. head로부터 끝 노드까지 순회

3. 링크 연결 작업

1. 추가할 데이터를 담을 노드 생성

2. head로부터 데이터 추가 위치 직전 노드까지 순회

3. 링크 연결 작업

• 데이터 삭제
• 데이터 추가와 반대의 작업 수행

연결 리스트 구성 코드

class Node {
	int data;
	Node next; // pointer

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

}

class LinkedList {
	Node head;

	public LinkedList(Node head){
		this.head = head;
	}
	
	// 연결 리스트 비어있는지 확인

	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; // 뒤에 따라오는 LinkedList가 없으면
		} 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.print(cur.data + " ");
            cur= cur.next;
        }
        System.out.println();
    }

}

단순 연결 리스트 구현 완성(노드 앞,중간,뒤 추가)

class LinkedList2 extends LinkedList {
    public 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 pre = cur;
            while (cur != null) {
                if (cur.data == beforeData) {
                    if(cur == this.head){
                        this.head = new Node(data, this.head); // 맨앞 노드 추가 후 헤드 옮김
                    } else {
                        pre.next = new Node(data, cur);
                    }
                break;
                }
            pre = cur;
            cur = cur.next;
            }
        }
    }

    public void removeData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        Node cur = this.head;
        Node pre = cur;
        while (cur != null) {
            if (cur.data == data) {
                if (cur == this.head) {
                    this.head = cur.next;
                } else {
                    pre.next = cur.next;
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }
}

양방향 연결 리스트(Doubly Linked List)

// Practice2
// 양방향 연결 리스트 (Doubly Linked List) 구현

class NodeBi {
    int data;
    NodeBi next;
    NodeBi prev;

    public NodeBi(int data, NodeBi next, NodeBi prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

class DoublyLinkedList extends LinkedList {
    NodeBi head;
    NodeBi tail;

    DoublyLinkedList(NodeBi node) {
        this.head = node;
        this.tail = node;
    }

    public boolean isEmpty() {
        if (this.head == null) {
            return true;
        }
        return false;
    }

    public void addData(int data, Integer beforeData) {
        if (this.head == null) {
            this.head = new NodeBi(data, null, null);
            this.tail = this.head;
        } else if (beforeData == null) {
            this.tail.next = new NodeBi(data, null, this.tail);
            this.tail = this.tail.next;
        } else {
            NodeBi cur = this.head;
            NodeBi pre = cur;
            while (cur != null) {
                if (cur.data == beforeData) {
                    if (cur == this.head) { // 헤드일 경우
                        this.head = new NodeBi(data, this.head, null);
                        this.head.next.prev = this.head;
                    } else { //헤드가 아닐 경우 == 중간에 데이터를 넣는 경우
                        pre.next = new NodeBi(data, cur, pre);
                        cur.prev = pre.next;
                    }
                    break;
                }
                pre = cur;
                cur = cur.next;
            }
        }
    }

    public void removeData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        NodeBi cur = this.head;
        NodeBi pre = cur;
        while (cur != null) {
            if (cur.data == data) {
                if (cur == this.head && cur == this.tail) { //노드가 하나인 상태
                    this.head = null;
                    this.tail = null;
                } else if (cur == this.head) {
                    this.head = cur.next;
                    this.head.prev = null; // 기존에 컬 head 제거
                } else if (cur == this.tail) {
                    this.tail = this.tail.prev; //기존 테일이 한 칸 앞으로 이동
                    this.tail.next = null;
                } else { //중간 노드 삭제
                    pre.next = cur.next;
                    cur.next.prev = pre;
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }

    public void showData() {
        if (this.isEmpty()) {
            System.out.println("list is empty!");
            return;
        }
        NodeBi cur = this.head; // head에서부터 tail까지 쭉 출력
        while(cur != null){
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();


    }

    public void showDataFromTail(){
        if(this.isEmpty()){
            System.out.println("List is empty!");
            return;
        }
        NodeBi cur = this.tail;
        while(cur != null){
            System.out.print(cur.data + " ");
            cur = cur.prev;
        }
        System.out.println();
    }
}