LinkedList

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

---

특징

자료의 순서는 정해져 있지만, 메모리 상에 연속성이 보장되지는 않음

시간복잡도

• 삽입: $O(1)$
• 삭제: $O(1)$
• 검색: $O(n)$

장점

• 데이터 공간을 미리 할당할 필요없음 (가변적)
• 추가, 삭제시 다른 인덱스에 변동이 없음
• 연속된 메모리 공간이 필요없다
• 무한개의 자료를 저장할 수 있다.

단점

• 연결구조를 위한 별도 데이터 공간 필요
• 연결 정보를 찾는 시간이 필요
• 데이터 추가, 삭제시 앞뒤 데이터의 연결을 재구성하는 작업 필요

---

구성

노드

데이터의 저장단위로 값과 포인터로 구성
메모리 안에서 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요는 없다.

데이터

리스트의 원소, 데이터값 저장

링크

다른 노드의 주소값 저장 (포인터)

class Node{
	int data;
    Node next;
}

헤드포인터

LinkedList의 첫번째 노드를 가리키는 변수

class LinkedList{
	Node head;
	LinkedList(){}
    LinkedList(Node node){
    	this.head = node;
	}
}

---

기본 연산

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

데이터 추가

tail

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

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);
    } 
}

head

• 추가할 데이터를 담을 노드 생성
• 링크 연결작업
• head 이전 작업

중간

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

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;
		}
    }
}

데이터 삭제

tail

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

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;
    }
}

head

• 삭제 노드 지정
• head 이전 작업
• delete_node 삭제

중간

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

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

데이터 탐색

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");
}

양방향 연결 리스트 구현

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

class DoubleLinkedList extends LinkedList{
	NodeBi head;
    NodeBi tail;
    DoubleLinkedList(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;
                } 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;
        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();
	}
    
}