3. Linked List

• Linked List
  • 연결 리스트, 링크드 리스트
  • 노드가 데이터와 포인터를 가지고 있고, 포인터는 다음 노드의 위치를 가지고 있는 구조이다.
  • Single Linked List는 다음 노드를 가리키는 하나의 포인터만 가지고 있다.
    • 
  • Double Linked List는 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있다.
    • 

 

• 장점
  • 데이터의 삽입과 삭제가 용이하다.
  • 리스트 내에서 자료의 이동이 필요하지 않다.
  • 사용 후 기억 장소의 재사용이 가능하다.
• 단점
  • 포인터 사용으로 인한 저장공간의 낭비가 있다.
  • 알고리즘이 복잡하다.
  • 특정 자료의 탐색 시간이 많이 소요된다.

 

• 구현 코드(Single Linked List와 Double Linked List가 있지만 본 내용에서는 Double Linked List만 구현하겠다.)
• 어떤 데이터가 들어올지 모르기 때문에 제네릭으로 타입을 잡아서 클래스를 구현했다.
• 노드

  • public class Node<T> {
    	T data;
        Node<T> prev = null;
        Node<T> next = null;
        
        public Node(T data) {
        	this.data = data;
        }
    }

  • 위의 설명에서 Double Linked List의 노드는 앞, 뒤로 포인터를 갖는다고 했다.
  • 노드는 데이터를 가지고 prev로 앞의 노드를 세팅, next로 뒤의 노드를 세팅한다.
• Linked List 클래스 생성
  

  • public class DoubleLinkedList<T> {
    	Node<T> head = null;
        Node<T> tail = null;
    }

• 삽입 메소드 작성

  • public void add(T data) {
    	if(this.head == null) {
        	this.head = new Node<T>(data);
            this.tail = this.head;
        } else {
        	Node<T> node = this.head;
            while(node.next != null) {
            	node = node.next;
            }
            node.next = new Node<T>(data);
            node.next.prev = node;
            this.tail = node.next;
        }
    }

  • 해당 리스트의 head가 null이라면 리스트가 비어있다는 의미이기 때문에 바로 데이터를 삽입해 준다.
  • 이때 head와 tail에 모두 들어온 data를 담은 node를 넣어준다.
  • 만약 head가 null이 아니라면 이미 리스트에 자료가 있기 때문에 리스트를 순회하면서 포인터가 null을 가리키는 곳까지 가서 데이터 삽입 작업을 해준다.
  • node클래스를 보면 내부에 next 필드가 존재함으로 node의 next가 null이 나올 때까지 리스트를 순회하며 null값이 나온다면 그곳에 node를 세팅해 준 후 세팅한 노드의 prev의 포인터를 세팅해 준다.
  • 마지막으로 리스트의 tail을 세팅해준 마지막 노드로 바꿔주면 삽입작업이 끝나게 된다.
• 삭제

  • public Node<T> delete(T data) {
    	if(this.head != null) {
        	Node<T> node = this.head;
            while(node.next != null) {
            	if(node.data == data) {
                	Node<T> prev = node.prev;
                    Node<T> next = node.next;
                    
                    node.prev.next = next;
                    node.next.prev = prev;
                    
                    return node;
                } else {
    				node = node.next;
                }
            }
        }
        
        return null;
    }

  • head가 null이라면 리스트에 아무것도 없기때문에 null을 리턴해 준다.
  • head가 null이 아니라면 리스트를 순회하며 데이터가 같은 값인지를 확인한 후 같은 값이라면 이전 노드와 다음 노드를 연결해서 해당 노드를 끊어낸 후 해당 노드를 반환한다.
• 검색

  • public T frontSearch(T data) {
    	if(this.head != null) {
    		Node<T> node = this.head;
            while(node.next != null) {
            	if(node.data == data) {
                	return node.data;
                } else {
                	node = node.next;
                }
            }
        } 
        return null;
    }
    
    public T tailSearch(T data) {
    	if(this.head != null) {
        	Node<T> node = this.tail;
            while(node != null) {
            	if(node.data == data) {
                	return node.data;
                } else {
                	node = node.prev;
                }
            }
        }
        return null;
    }

  • 검색은 head 혹은 tail부터 검색을 할 수 있다.
  • head는 next를 사용해 순회하면 되고 tail은 prev를 사용해 순회하면 된다.