[JAVA] List - LinkedList

LinkedList는 List인터페이스를 구현한다.

   이 말은 즉 List인터페이스를 구현했기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.

Linked List의 요소

  Linked List의 각 요소는 우리가 많이 들어봤듯이 노드(Node)라 불린다.

  이 노드들은 자신과 연결된 다음 요소에 대한 참조(주소값) + 자신의 데이터로 구성된다.

class Node // 단방향
{
      Node next; // 다음 요소의 주소
      Object obj; // 현재 요소의 데이터
}

ArrayList와 Vector 같은 배열의 단점을 보완하기 나왔다.

  배열은 모든 데이터가 연속적으로 존재하지만 LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태이다.

[그림1] Linked List VS Array List

  여기 위에서 33의 값을 지우려면 어떻게 해야하는가 ? 

33의 주소값을 66의 주소값으로 넣어주고 33노드의 주소값을 NULL로 만들면 된다.

코드를 짜보려고 하는 순간 우리는 생각해봐야한다.

"어? 33의 주소값을 찾으려면 head(66) 노드에서 시작해서 33 노드까지 가야되네?"

그것을 보안하려면 이전 노드에 대한 참조(주소)를 알면 된다.

 

참고로 LinkedList클래스는 이름과 달리 Double Linked List 로 구현이 되있다. (양방향)

class Node // 양방향
{
	Node next; // 다음 노드의 주소값
        Node pre; // 이전 노드의 주소값
        Object obj; // 자신의 값
}

자 이제 33을 지워보자. 

 

public void myRemove(Node whatRemove){

      Node preNode = whatRemove.pre; // 이전 노드의 주소
      Node nextNode = whatRemove.next; // 다음 노드의 주소

      // 자 이제 삭제할 노드(whatRemove)의 이전 노드's 주소's next노드를 이어주자.
      preNode.next = whatRemove.next;

      // 다음 노드의 previous 주소를 이전 노드의 next 주소에 넣어주면 끝이난다.
      nextNode.pre = previous.next;
    
}
    
    

LinkedList는 읽어오는 시간이 느리지만 비순차적인 추가/삭제는 빠르다.

 

참고문헌

[그림 1] 출처 : http://www.nextree.co.kr/p6506/

JAVA의 정석 [ 남궁 성 지음 ]