1. 링크드 리스트(Linked List) 구조

• 연결 리스트라고도 합니다.
• Linked List는 떨어진 곳에 존재하는 데이터를 주소로 연결하여 관리하는 데이터 구조입니다.

LinkedList 기본 구조와 용어

• 노드(Node): 데이터 저장 단위(데이터값, 포인터)로 구성됩니다.

• 포인터(pointer): 각 노드 안에서 다음이나 이전의 노드와의 연결 정보(주소)를 가지고 있는 공간입니다.

• 일반적인 LinkedList 형태

그림 추가

2. LinkedList 예시

Node 클래스 구현

public clfgass Node<T>{
	T data; // 데이터
    Node<T> next = null; // 포인터 역할
    
    public Node(T data){
    	this.data = data;
    }
}

Node와 Node 연결하기(Node 인스턴스간 연결)

Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node2 = new Node<Integer>(2);

node1.next = node2;
Node head = node1;

LinkedList 데이터 추가

public class SingleLinkedList<T>{
	public Node<T> head = null;
    
    public class Node<T>{
    	T data;
        Node<T> next = null;
        
        public Node(T data){
        	this.data = data;
        }
    }
    
    public void addNode(T data){
    	if(head == null){
        	head = new Node<T>(data);
        }else{
        	Node<T> node = this.head;
            while(node.next != null){
            	node = node.next;
            }
            node.next = new Node<T>(data);
        }
    }
    
    public void printAll(){
    	if(head != null){
        	Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null){
            	node = node.next;
          		System.out.println(node.data);
            }
        }
    }
}

LinkedList 데이터 출력(조회)

3. LinkedList 장단점

장점

• 이전, 다음 데이터 값에 대한 주소를 포함하고 있으므로 연속된 데이터 공간이 필요가 없습니다. 따라서 데이터 공간을 미리 할당하지 않아도 됩니다.

단점

• 데이터 값에 대한 주소를 갖기 위한 데이터 공간이 필요하므로 저장공간 효율이 높지 않습니다.
• 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느립니다(LinkedList는 항상 맨 앞의 데이터부터 찾아서 다음 주소값을 찾는 작업이 필요하기 때문입니다)
• 중간 데이터가 삭제되는 경우 앞 뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요합니다.

4. LinkedList 데이터 사이에 데이터를 추가, 삭제

• LinkedList는 유지 관리에 부가적인 구현이 필요합니다.

public class SingleLinkedList<T>{
	public Node<T> head = null;
    
    public class Node<T>{
    	T data;
        Node<T> next = null;
        
        public Node(T data){
        	this.data = data;
        }
    }
    
    public void addNode(T data){
    	if(head == null){
        	head = new Node<T>(data);
        }else{
        	Node<T> node = this.head;
            while(node.next != null){
            	node = node.next;
            }
            node.next = new Node<T>(data);
        }
    }
    
    public void printAll(){
    	if(head != null){
        	Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null){
            	node = node.next;
          		System.out.println(node.data);
            }
        }
    }
    
    public Node<T> search(T data){
    	if(this.head == null){
        	return null;
        }else{
        	Node<T> node = this.head;
            while(node != null){
            	if(node.data == data){
                	return node;
                }else{
                	node = node.next;
                }
            }
            return null;
        }
    }
    
    public void addNodeInside(T data, T isData){ // data는 현재 Node의 data, isData는 현재 Node가 저장할 위치의 이전 data
    	Node<T> searchedNode = this.search(isData);
        
        if(searchedNode == null){
        	this.addNode(data);
        }else{
        	Node<T> nextNode = searchedNode.next;
            searchedNode.next = new Node<T>(data);
            searchedNode.next.next = nextNode;
            
        }
    }
    
    public boolean delNode(T isData){
    	if(this.head == null){
        	return false;
        }else{
        	Node<T> node = this.head;
            if(node.data == isData){
            	this.head = this.head.next;
                return true;
            }else{
            	while(node.next != null){
                	if(node.next.data == isData){
                    	node.next = node.next.next;
                        return true;
                    }
                    node = node.next;
                }
                return false;
            }
        }
    }
    
}

• Node 추가

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

linkedList.addNode(1);
linkedList.addNode(2);
linkedList.addNode(3);

linkedList.printAll();
System.out.println("===");

linkedList.addNodeInside(5, 1);
linkedList.printAll();
System.out.println("===");

linkedList.addNodeInside(7, 20);
linkedList.printAll();

결과
1
2
3
===
1
5
2
3

===
1
5
2
3
7

• Node 삭제

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

linkedList.addNode(1);
linkedList.addNode(2);
linkedList.addNode(3);

linkedList.printAll();
System.out.println("===");

System.out.println(delNode(3));
System.out.println(delNode(3));

결과
1
2

3

true
false