연결리스트(Linked List)

정의

---

 

 

각 노드가 데이터와 레퍼런스를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

종류

---

• 단일 연결리스트 
  • 리스트에 들어가는 각 데이터 원소에는 리스트의 다음 원소에 대한 연결고리(link, 포인터 또는 레퍼런스)가 들어가있다.
  • 첫번째 원소 : HEAD
  • 마지막 원소 : TAIL
  • 리스트에 있는 모든 원소의 위치를 파악하기 위해서는 리스트의 첫 번쨰 원소에 대한 포인터나 레퍼런스가 있어야만 한다. 그 포인터나 레퍼런스는 보통 별도의 자료구조에 저장함.

public class LinkedList{
  private Node head; //누가 첫번째 변수인가
  private Node tail; //누가 마지막 변수인가
  private int size =0; //몇 개의 element가 이 리스트 안에 담겨 있는가

  private class Node{
    private Object data; //하나의 엘리먼트(=Node)가 하나의 객체
    private Node next;   //누가 다음 노드인지 정의, 다음 노드의 데이터타입은 Node
    public Node(Object input){  //input : 노드가 처음 들어갔을 때 값이 전달됨
        this.data =input;
        this.next =null;
    }
    public String toString(){
        return String.valueOf(this.data);
      }

    }
  }
}

 

 

• 이중 연결 리스트 
  • 각 원소마다 리스트에서 그 다음에 오는 원소에 대한 연결고리 외에 그 앞에 있는 원소에 대한 연결고리도 들어있음.
  • 연결고리를 추가함으로써 리스트를 어느 방향으로든 종주할 수 있음.