[자료구조] LinkedList 연결리스트란?

혹시 Node가 뭔지 모른다면 다음의 포스트를 보고오자.

노드..? 그래프..? 트리..? 난모르겠어!

연결리스트란? Node로 이루어진 리스트이다.

?? 그럼 배열과 차이점이 뭐에요?

많은 차이점이 존재하지만, 필자가 생각하는 가장 큰 차이점은 다음과 같다.

메모리상의 연속적인 주소를 가지지 않아도 된다.

위와 같은 특징덕분에 어떤 데이터를 삭제했을때, 해당노드의 전,후의 노드를 연결하기만 하면 해결되기 때문에 배열보다 속도가 빠르다.

실제 코드를 구현해가며 따라해보자.

// Node는 자신에대한 정보와, 다음경로에대한 정보 2가지를 가진다.
    static class Node {
        static int NODE_MAX = 5000;
        int data;
        Node next;

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

    // LinkedList는 시작위치(head), 마지막위치(tail)을 갖는다.
   //nodeCnt는 현재 노드의 크기를 의미하고
  // nodeArr은 노드List이다.
    static class LinkedList {
        Node head;
        Node tail;
        Node[] nodeArr;
        int nodeCnt;

        public LinkedList() {
            head = null;
            nodeArr = new Node[NODE_MAX];
            nodeCnt = 0;
        }
        Node getNewNode(int data) {  // data를 값으로 갖는 새로운 node 생성하고, 생성된 node를 return
            nodeArr[nodeCnt] = new Node(data);
            return nodeArr[nodeCnt++];
        }
    }

// insert(삽입)은 2가지 경우로 나눌 수 있다.
// 맨앞에 넣기
// 중간or맨뒤에 넣기
//노드가 1개가 아닌 리스트에 리스트가 insert될 수도 있다.
void insert(int idx, int[] nums){
    int st = 0;
    // 맨앞에 넣기
    if(idx ==0){ 
     //한 개만 추가하고 head 재조정하기
      if(head != null){
        Node newNode = getnewNode(nums[0]);
        newNode.next = head;
        head = newNode;
      }
      else{
          head = getNewNode(nums[0];
      }
    }
    남은 수들을 head 뒤에 차례로 이어 붙이기
    idx = 1;
    st = 1;
   Node cur = head;
   //idx개만큼 이동하기
   for(int i=1; i<idx; i++){
      cur = cur.next;
   }

   for(int i =st; i<nums.length; i++){
     Node newNode = getNewNode(nums[i]);
     newNode.next = cur.next;
     cur.next = newNode;
     cur = newNode; 
   }
   if(cur.next == null){
     tail = cur;
   }

}

// idx 인덱스부터 cnt개 지우기!
// 마찬가지로 head를 지우느냐 아니냐 2가지로 나눌 수 있다.
void delete(int idx, int cnt){
Node cur = head;
    if(idx == 0){
        for(int i=0; i<cnt; i++){
            cur = cur.next;
        }
        head = cur;
        return;
    }

    //idx개 만큼 이동하기
    for(int i=1; i<idx; i++){
        cur = cur.next;
    }
    Node anchor = cur; // 삭제되기 직전 위치 기억하기
    for(int i=0; i<cnt; i++){
        cur = cur.next;
    }
    anchor.next = cur.next;

    if(anchor.next == null){
        tail = anchor;
    }
}

// 맨뒤에 data추가하기!
void add(int data){ 
    Node cur = tail;
    Node newNode = getNewNode(data);
    cur.next = newNode;
    tail = newNode;
}

// 리스트 출력하기!
// 우선 10개만 출력하는건데, 취향껏 작성하면된다.
void print() throws Exception{
    int cnt = 10;
    Node cur = head;
    while(--cnt >=0){
        bw.write(cur.data +" ");
        cur = cur.next;
    }
}