[Java] 연결리스트(Linked List)와 이중 연결리스트(Doubly linked list), 이중 원형 연결리스트(Doubly circular linked list)

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

 

 

연결 리스트(Linked List)

 

배열의 단점  크기를 변경할 수 없다. - 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야함 - 실행속도를 향상시키려면 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다. - 차례대로 데이터를 추가하고 데이터를 삭제하는 것은 빠르지만 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(접근시간, access time)이 가장 빠르다는 장점이 있지만 크기를 변경할 수 없다는 것과 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다는 단점이 있다.

 

 

배열과 링크드 리스트

 

class Node{
    Node next;	//다음 요소의 주소
    Object obj	//데이터
}

이러한 배열의 단점을 보완하기 위한 것이 링크드 리스트(linked list)이다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link) 한 형태로 구성되어 있다. 위의 그림을 보면 링크드 리스트의 각 요소( node )들은 자신과 연결된 다음 요소에 대한 참조(주소 값)와 데이터로 구성되어있다. 링크드 리스트에서의 데이터 삭제는 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 되어 매우 간단하다. 추가할 때도 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그다음 요소를 참조하도록 변경하기만 되어서 처리속도가 매우 빠르다.

 

 

 

 

이중 연결 리스트(Doubly linked list)

 

class Node{
    Node next;	//다음 요소의 주소
    Node previous;	//이전 요소의 주소
    Object obj;	//데이터
}

링크드 리스트는 이동방향이 단방향이기 때문에 이전 요소에 대한 접근은 어렵다. 이점을 보완한 것이 더블 링크드 리스트(이중 연결리스트, doubly linked list)이다. 더블 링크드 리스트는 단순히 링크드 리스트에 참조 변수를 하나 더 추가하여 이전 요소에 대한 참조가 가능하도록 했을 뿐 나머지는 링크드 리스트와 같다. 더블링크드 리스트는 링크드 리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 더 많이 사용된다.

 

실제로  LinkedList 클래스는 이름과 달리 '링크드 리스트'가 아닌 '더블 링크드 리스트'로 구현되어 있는데, 이는 링크드 리스트의 단점인 낮은 접근성(accessability)을 높이기 위한 것이다.

 

생성자 or 메서드	설  명
LinkedList( )	LinkedList 객체를 생성
LinkedList(Collection c)	주어진 컬렉션을 포함하는  LinkedList 객체를 생성
boolean add(Object o)	지정된 객체( o )를  LinkedList 의 끝에 추가 성공하면 true, 실패하면 false 반환
void add(int index, Object element)	지정된 위치( index )에 객체( element )를 추가
boolean addAll(Collection c)	주어진 컬렉션에 포함된 모든 요소를  LinkedList 의 끝에 추가 성공하면 true, 실패하면 false 반환
boolean addAll(int index, Collection c)	지정된 위치( index )에 주어진 컬렉션에 포함된 모든 요소를 추가 성공하면 true, 실패하면 false 반환
void clear( )	LinkedList 의 모든 요소를 삭제
boolean contains(Object o)	지정된 객체가  LinkedList 에 포함되었는지 알려줌
boolean containsAll(Collection c)	저장된 컬렉션의 모든 요소가 포함되었는지 알려줌
Object get(int index)	지정된 위치( index )의 객체를 반환
int indexOf(Object o)	지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환
boolean isEmpty( )	LinkedList 가 비어있는지 알려준다. 비어있으면 true, 비어있지 않으면 false 반환
Iterator iterator( )	Iterator 를 반환한다.
int lastIndexOf(Object o)	지정된 객체의 위치( index )를 반환(끝부터 역순검색)
ListIterator listIterator( )	ListIterator 를 반환
ListIterator listIterator(int index)	지정된 위치에서부터 시작하는  ListIterator 를 반환
Object remove(int index)	지정된 위치( index )의 객체를  LinkedList 에서 제거
boolean remove(Object o)	지정된 객체를  LinkedList 에서 제거 저장에 성공하면 true, 실패하면 false 반환
boolean removeAll(Collection c)	지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
boolean retainAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
Object set(int index, Object element)	지정된 위치( index )의 객체를 주어진 객체로 바꿈
int size( )	LinkedList 에 저장된 객체의 수를 반환
List subList(int fromIndex, int toIndex)	LinkedList 의 일부를  List 로 반환
Object[ ] toArray( )	LinkedList 에 저장된 객체를 배열로 반환
Object[ ] toArray(Object[ ] a)	LinkedList 에 저장된 객체를 주어진 배열에 저장하여 반환
Object element( )	LinkedList 의 첫번째 요소를 반환
boolean offer(Object o)	지정된 객체( o )를  LinkedList 끝에 추가 저장에 성공하면 true, 실패하면 false 반환
Object peek( )	LinkedList 의 첫번째 요소를 반환
Object poll( )	LinkedList 의 첫번째 요소를 반환,  LinkedList 에서는 제거된다.
Object remove( )	LinkedList 의 첫번째 요소를 제거
void addFirst(Object o)	LinkedList 의 맨 앞에 객체( o )를 추가
void addLast(Object o)	LinkedList 의 맨 끝에 객체( o )를 추가
Iterator descendingIterator( )	역순으로 조회하기 위한  DescendingIterator 를 반환
Object getFirst( )	LinkedList 의 첫번째 요소를 반환
Object getLast( )	LinkedList 의 마지막 요소를 반환
boolean offerFirst(Object o)	LinkedList 의 맨 앞에 객체를 추가 성공하면 true, 실패하면 false 반환
boolean offerLast(Object o)	LinkedList 의 맨 끝에 객체를 추가 성공하면 true, 실패하면 false 반환
Object peekFirst( )	LinkedList 의 첫번째 요소를 반환
Object peekLast( )	LinkedList 의 마지막 요소를 반환
Object pollFirst( )	LinkedList 의 첫번째 요소를 반환하면서 제거
Object pollLast( )	LInkedList 의 마지막 요소를 반환하면서 제거
Object pop( )	removeFirst( ) 와 동일
void push(Object o)	addFirst( ) 와 동일
Object removeFirst( )	LinkedList 의 첫번째 요소를 제거
Object removeLast( )	LinkedList 의 마지막 요소를 제거
boolean removeFirstOccurrence(Object o)	LinkedList 에서 첫번째로 일치하는 객체를 제거
boolean removeLastOccurrence(Object o)	LinkedList 에서 마지막으로 일치하는 객체를 제거

 LinkedList 는  Queue 인터페이스와  Deque 인터페이스를 구현하도록 변경되었는데 마지막 22개의 메서드는  Queue 인터페이스(회색 글씨)와  Deque 인터페이스(나머지)를 구현하면서 추가된 것이다.

 

 

 

이중 원형 연결 리스트(Doubly circular linked list)

  더블 링크드 리스트의 접근성을 보다 향상시킨 것인데, 단순히 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다. 마지막 요소의 다음 요소가 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다. 

 

 

 

 

Linkedlist와 ArrayList의 차이점

컬렉션	읽기(접근시간)	추가 / 삭제	특  징
ArrayList	빠름	느림	순차적이 추가삭제는 더빠름 비효율적인 메모리사용
LinkedList	느림	빠름	데이터가 많을수록 접근성이 떨어짐

1. 순차적으로 추가/삭제하는 경우에는  ArrayList 가 더 빠르다.
    ArrayList 의 크기가 충분하지 않으면, 새로운 크기의  ArrayList 를 생성하고 데이터를 복사하는 일이 발생하게 되므로 순차적으로 데이터를 추가해도  ArrayList 가  LinkedList 가 더 느릴 수 있다.
   
   
2. 중간에 데이터를 추가/삭제하는 경우에는  LinkedList 가 더 빠르다.
    LinkedList 는 각 요소 간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠른 반면  ArrayList 는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야 하기 때문에 처리속도가 늦다.
   
   

package Example;

import java.util.*;

public class Example {
	public static void main(String[] args) {
		//추가할 데이터의 개수를 고려해서 크기를 지정해야함
		ArrayList al = new ArrayList(2000000);
		LinkedList ll = new LinkedList();
		
		System.out.println("=== 순차적으로 추가하기 ===");
		System.out.println("ArrayList : " + add1(al));
		System.out.println("LinkedList : " + add1(ll));
		System.out.println();
		
		System.out.println("=== 중간에 추가하기 ===");
		System.out.println("ArrayList : " + add2(al));
		System.out.println("LinkedList : " + add2(ll));
		System.out.println();
		
		System.out.println("=== 중간에서 삭제하기 ===");
		System.out.println("ArrayList : " + remove2(al));
		System.out.println("LinkedList : " + remove2(ll));
		System.out.println();
		
		System.out.println("=== 순차적으로 삭제하기 ===");
		System.out.println("ArrayList : " + remove1(al));
		System.out.println("LinkedList : " + remove1(ll));
		System.out.println();
	}
	
	public static long add1(List list) {
		long start = System.currentTimeMillis();
		for(int i = 0 ; i < 1000000 ; i++) list.add(i+"");
		long end = System.currentTimeMillis();
		return end - start;
	}
	
	public static long add2(List list) {
		long start = System.currentTimeMillis();
		for(int i = 0 ; i < 10000 ; i++) list.add(500,"X");
		long end = System.currentTimeMillis();
		return end - start;
	}
	
	public static long remove1(List list) {
		long start = System.currentTimeMillis();
		for(int i = list.size() - 1 ; i >= 0 ; i--) list.remove(i);
		long end = System.currentTimeMillis();
		return end - start;
	}
	
	public static long remove2(List list) {
		long start = System.currentTimeMillis();
		for(int i = 0 ; i < 10000 ; i++) list.remove(i);
		long end = System.currentTimeMillis();
		return end - start;
	}
}

실행결과

데이터의 추가 / 삭제 시 성능 차이를 확인하는 예제이다. (컴퓨터마다 성능의 차이가 있을 수 있다) 데이터의 개수가 크지 않다면 큰 차이가 나지 않겠지만 많은 데이터를 다룰 때에는  ArrayList 와  LinkedList 의 장단점을 고려해서 적절하게 사용하는 것이 좋다.

 

 

package Example;

import java.util.*;

public class Example {
	public static void main(String[] args) {
		ArrayList al = new ArrayList(1000000);
		LinkedList ll = new LinkedList();
		
		add(al);
		add(ll);
		
		System.out.println("=== 접근시간 테스트 ===");
		System.out.println("ArrayList : " + access(al));
		System.out.println("LinkedList : " + access(ll));
	}
	
	public static void add(List list) {
		for(int i = 0 ; i < 1000000 ; i++) list.add(i+"");
	}
	
	public static long access(List list) {
		long start = System.currentTimeMillis();
		for(int i = 0 ; i < 1000000 ; i++) list.get(i);
		long end = System.currentTimeMillis();
		return end - start;
	}
}

 

실행결과

접근시간의 차이를 확인하는 예제이다(컴퓨터마다 성능의 차이가 있을 수 있다) 배열의 경우 자료를 순차적으로 저장하기 때문에 간단한 계산( index 의 값을 알 경우에  배열주소 + (index값 * 데이터타입의 크기))만으로 해당하는 요소의 주소를 얻을 수 있지만  LinkedList 는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 찾고자 하는 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다. 그래서  LinkedList 는 데이터의 개수가 많아질수록 접근시간(데이터를 읽어오는 시간, access time)이 길어진다는 단점이 있다.