[Java] 자바의 LinkedList

 

 

 

  배열은 데이터를 묶어 놓은 것으로 구조가 간단하고 데이터가 연속적으로 존재한다. 사용하기도 쉽고 데이터를 읽어 올 때는 걸리는 시간이 가장 빠르다는 장점도 가지고 있다. 

 

  배열은 장점만 가지고 있는 것은 아니다. 단점으로는 

 

  1. 크기를 변경할 수 없다.

크기를 변경할 수 없으므로 만약 배열 저장공간이 부족할 시 더 큰 배열을 생성하고 공간이 부족한 배열의 값들을 복사하고 참조를 변경해야 한다. 이런 과정으로 프로그램 동작 시간이 오래 걸린다. 충분히 큰 크기의 배열을 미리 생성시켜도 메모리가 낭비된다.

 

   2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다. (추가&삭제에 단점이 많음)

차례대로 데이터를 추가하고 배열의 마지막 위치에 있는 데이터들은 삭제하기 쉽고 빠르지만, 배열의 중간에 데이터를 추가한다면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 하는 번거로움이 있다.

 

 

  한마디로 Array의 장점은 사용하기 쉽고, 데이터를 읽을 때 빠르다는 장점이 있고 단점으로는 비순차적인 데이터 추가 및 삭제에서는 시간이 오래 걸리는 점, 배열의 size(크기)를 변경할 수 없다는 점이 있다.

 

 

 

 

---

 

 

 

🎈LinkedList란?

  Collection 프레임워크의 일부이며 java.util 패키지에 있는 클래스이다.

 

  Array와 달리 LinkedList는 불연속적으로 데이터들이 존재한다. 그 데이터들은 서로 연결한 형태로 구성되어 있다.

각각의 노드로 연결했다고 표현한다. 

 

[그림 1] Node 구성도

 

 

  위 [그림 1]처럼 Node는 각 요소들은 자신의 다음 요소와 연결하여 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다. LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(link) 한 형태로 구성되어 있다.

 

 

  노드(node)란, 데이터가 저장되는 객체를 뜻한다. 보통 첫 번째 node를 head라고 부른다. 

 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
 }

  위 코드는 LikedList$Node.class 파일에서 복사해서 붙여 넣은 것이다. 코드에서 Node 클래스는 멤버 변수가 item과 next, prev 단 세 가지가 있다. 

 

  노드는 데이터를 적제한 변수와 다음 요소를 연결하기 위한 참조변수(주소값이 들어갈) 하나, 자신을 연결한 이전 요소의 주소값 이렇게 3가지로 구성된다.   (이 코드는 Doubly-linked list입니다.)

 

  Doubly-linked list와 Singly-linked list의 차이는 Doubly는 이전 노드와 다음 노드를 참조하지만 Singly는 다음 노드만 참조하도록 구성되어 있다.

---

 

 

 

 

🎈LinkedList 추가와 삭제

  

  LinkedList는 데이터의 추가와 삭제가 간단하다. 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 된다. 하나의 참조만 변경하면 되는 것이다. 이러한 이유로 LinkedList는 비순차적인 추가와 삭제에서도 Array와 다르게 더 빠른 것이다. Array는 복사하는 과정 때문에 늦었다면 LinkedList는 복사하는 과정이 필요 없다. (물론 순차적 추가 삭제는 Array가 더 성능이 좋다.)

 

 

 

  이것으로 배열(Array)의 장점은 

• 검색이 LinkedList보다 빠르다.
• 순차적 추가 삭제는 LinkedList보다 빠르다.

  다음으로 링크드 리스트(LinkedList)의 장점은

• 비순차적 추가 삭제는 Array보다 더 좋은 성능을 가지고 있다.
• 추가 삭제하기도 구조적으로 편하다.

 

 

 

 

 

 

  Linked List에서 데이터 삭제는 간단하다. 삭제하고자 하는 요소의 이전 요소를 삭제하고자 하는 요소의 다음 요소를 참조하도록 바꿔주기만 하면 된다. 단 하나의 참조만 변경하면 삭제는 쉽게 할 수 있다.

 

  Linked List의 추가 역시 새로운 요소를 생성한 후 추가할 위치의 이전 요소의 참조를 새롭게 추가될 요소로 참조하도록 변경하고 새로운 요소는 그다음 요소를 참조하면 된다.

---

 

🎈LinkedList와 ArrayList 구조적 차이

  밑에 그림은 위에 arr은 Array 밑에는 LinkedList이다. ArrayList는 그림과 같이 요소들이 연속적으로 존재한다. 메모리에서도 요소들이 연속적으로 존재하기 때문에 간단한 계산만으로 요소의 주소 값을 쉽게 얻을 수 있다.

  배열의 경우 데이터 주소를 계산하기 위해서

인덱스가 n인 데이터 주소 = 배열의 주소+(n*데이터 타입의 크기) 

  예를 들어 int 배열은 데이터의 타입 크기가 4byte이다. 

  배열의 주소가 0*100이라면 index 0인 요소의 데이터 주소는

  0*100+(0*4) = 0*100   --> [0]의 데이터 주소

  배열의 주소가 0*100이라면 index 2인 요소의 데이터 주소는

  0*100+(2*4)= 0*108  --> [2]의 데이터 주소

 

 

 

 

 

 

  LinkedList나 ArrayList 둘 다 List 인터페이스를 이용해 만들어진 것이라 List의 다양한 메서드들을 사용할 수 있다. 

 

 

---

 

  1.LinkedList 선언

 

import java.util.Arrays;
import java.util.LinkedList;

LinkedList list1 = new LinkedList(); // 타입 미설정 기본값 Object
LinkedList<Object> list2 = new LinkedList<Object>(); // Object 타입
LinkedList<Integer> list3 = new LinkedList<Integer>(); // Integer 타입
LinkedList<Integer> list4 = new LinkedList<>(); // 타입 선언 생략
LinkedList<Integer> list5 = new LinkedList<>(Arrays.asList(1, 2, 3)); // 초기값 선언
LinkedList<Object> list6 = new LinkedList<>(list2);  //다른 LinkedList값으로 초기화

  다양한 형태의 타입으로 세팅할 수 있다. class, String, Double 등 

 

  list5처럼 선언과 동시에 초기값을 선언할 수 있다. Arrays.asList(value1, value2, ....)

  list6처럼 다른 Collection값으로 초기화할 수 있다.

 

Stack st = new Stack();
st.push("안녕?");
LinkedList list = new LinkedList(st);
System.out.println(list);

예를 들어 Stack 역시 Collection의 자손으로 LinkedList를 선언할 때 Stack으로 구성된 데이터를 받을 수 있다.

 

---

 

 2-1.LinkedList 추가

public class LinkedExample {

	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<>();
		list.add(0); //list에 0추가
		System.out.println("list: "+list);
		
		list.add(150); //list에 150추가
		System.out.println("list: "+list);
		
		list.add(1,300); //list index 1에 300추가
		System.out.println("list: "+list); 
	}
}

 

 

  LinkedList는 List인터페이스를 구현한 것으로 List의  int size(), boolean isEmpty(), boolean add() 등 값을 추가하고 삭제하는 다양한 메서드들을 사용할 수 있다. 

 

  위 코드처럼

 

  add(E e): 메서드 값을 추가하면 마지막 index의 다음 공간을 생성해 추가한다.  e는 Object이므로 데이터의 종류 상관없이 모두 추가할 수 있다.

  add(int index, E element): 는 매개변수로 받은 index 값의 위치에 데이터를 추가한다.

 

index: index at which the specified element is to be inserted (명시된 index값에 element를 넣는다.)

element: element to be inserted (삽입될 요소)

 

LinkedList<Integer> list = new LinkedList<>();
list.add(50);
list.addFirst(25);  //리스트 가장 앞에 데이터 추가
list.addLast(75);  //리스트 가장 뒤에 데이터 추가
System.out.println(list);

addFirst()와 addLast() 메서드는 리스트의 가장 앞이나 뒤에 데이터를 추가해주는 메서드이다.

 

 

 

2-2.LinkedList 삭제

import java.util.LinkedList;

public class LinkedExample {

	public static void main(String[] args) {
		LinkedList<String> sList = new LinkedList<String>();
		sList.add("apple");
		out(sList);
		sList.add("pineapple");
		out(sList);
		
		LinkedList<String> sList2 = new LinkedList<>(sList); //sList값으로 초기화
		System.out.println("==리스트 삭제==");
		for(int i=sList.size()-1; i>=0;i--) {
			sList.remove(i);  //remove() 리스트 값 하나씩 삭제
			out(sList);
		}
		
		System.out.println("sList2: "+sList2);
		System.out.println("==리스트 값 한번에 삭제==");
		sList2.clear();  //clear() 리스트 값 한번에 삭제
		System.out.println("sList2: "+sList2);
	}
	// 리스트 호출 사용자 메서드
	static void out(LinkedList list) {
		System.out.println("sList: "+list);
	}
}

출력결과

 

 

  링크드 리스트의 데이터 삭제 메서드는 remove()와 clear() 등 이 존재한다.

 

remove() 는 리스트의 맨 마지막 데이터를 삭제한다. 

clear() 는 리스트의 데이터들을 전부 삭제한다. (데이터만 삭제되고 List는 완전히 삭제되지 않는다. 계속 JVM 메모리 Heap 부분에 존재하고 있다.)

 

remove()메서드에 대해 자세히 알아보면

 

(Type1) remove(int index): index의 위치한 데이터를 삭제한다.
(Type2) remove(): 생략 시 index0에 위치한 데이터를 삭제한다.(맨 앞 데이터 삭제)  
                                Time complexity: O(n)
(Type3) remove(Object o): 아무 데이터 타입이나 삭제한다. String, float 등 모든 데이터 
                                              Time complexity: O(n)

 

LinkedList<String> sList = new LinkedList<String>();
sList.add("아기");
sList.add("돼지");
sList.add("^^");
System.out.println("sList:"+sList);
sList.removeLast();
System.out.println("sList:"+sList);
sList.removeFirst();
System.out.println("sList:"+sList);

  removeLast(), removeFirst() 역시 리스트의 맨 처음이나 마지막 부분의 데이터를 삭제하는 메서드이다.

 

 

 

3. LinkedList 크기 

 

LinkedList<String> sList = new LinkedList<String>(Arrays.asList("A","B","C","D"));
System.out.println("sList:"+sList);
System.out.println(sList.size());  //Integer 데이터 타입으로 4 return

 

 

 

4. LinkedList 값 가져오기

import java.util.Arrays;
import java.util.LinkedList;

public class LinkedExample {

	public static void main(String[] args) {
		LinkedList<Integer> sList = new LinkedList<>(Arrays.asList(1,2,3,4));
		int first_listValue = sList.get(0);
		System.out.println(first_listValue);
		System.out.println(sList.getLast());
        
		System.out.println("=====");
        
		for(int i:sList) {  
        	//반복문을 통해 List 값 차례대로 가져오기
			System.out.println(sList.get(i-1));  
		}
		
	}
	
}

출력결과

 

public E get(int index) 메서드는 index에 해당하는 데이터 값을 return 해준다. 

ArrayList에서 사용하는 get()과 LinkedList에서 사용하는 get()은 속도 차이가 난다. LinkedList가 훨씬 느리다.

 

 

 

 

5. LinkedList 값 검색

LinkedList<Integer> sList = new LinkedList<>(Arrays.asList(1,2,3,4));
System.out.println(sList.contains(3));  //값 3 검색 있으면 true
System.out.println(sList.contains(30)); //없으면 false
		
System.out.println(sList.indexOf(2));  //값 2에 해당하는 index값 출력
System.out.println(sList.lastIndexOf(1));  //뒤에서부터 검색
System.out.println(sList.indexOf("System"));  //없으면 -1을 출력

출력결과

public int indexOf (Object o)

public int contains (Object o)

public int lastIndexOf (Object o)

 

 

 

 

 

참고한 좋은 글들

https://www.nextree.co.kr/p6506/

자료구조: Linked List 대 ArrayList

https://coding-factory.tistory.com/552

[Java] 자바 LinkedList 사용법 & 예제 총정리