LinkedList의 개념과 구현

LinkedList란 ?

LinkedList는 ArrayList와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 통해 리스트를 구현합니다. 배열과는 다르게 LinkedList는 데이터의 위치가 흩어져있기 때문에 서로 연결되어있어야 합니다. LinkedList는 자료구조에서 다양하게 사용되기 때문에 개념을 잘 이해해야 합니다.

 

용어를 정리해봅시다. array list에서는 엘리먼트라는 이름을 사용했지만 linked list와 같이 연결된 엘리먼트들은 노드(node, 마디, 교점의 의미) 혹은 버텍스(vertex, 정점, 꼭지점의 의미)라고 부릅니다. 이런 용어들은 연결성이 강조된 표현이라고 생각하시면 됩니다. 엘리먼트, 노드, 버텍스 모두 같은 의미입니다.

 

 

LinkedList의 특징

 

- LinkedList의 사이즈는 프로그램 실행중에 커지거나 작아질 수 있습니다. 아래 구현 소스코드를 살펴보면 size 변수를 통해 LinkedList의 사이즈를 알 수 있습니다.

- Array와 달리 고정된 할당 메모리가 없으므로 엘리먼트가 늘어나는 경우 Array보다 활용이 용이합니다.

- 다음 노드의 위치 정보만 가지고 있으며 인덱스를 가지고 있지 않기 때문에 탐색시 순차접근(sequential access)만 가능합니다. 따라서 노트 탐색 시 시간이 많이 소요될 수 있습니다.

- 노드 추가/삭제는 위치정보의 수정만으로 가능하기 때문에 성능이 좋습니다

 

 

LinkedList의 구조

 

LinkedList의 노드는 최소한 두 가지 정보를 알고 있어야 합니다. 노드의 값과 다음 노드입니다. 각각의 노드가 다음 노드를 알고 있기 때문에 하나의 연결된 값의 모임을 만들 수 있는 것입니다.

 

이를 구현하는 방법은 여러가지입니다. 만약 사용 언어가 C라면 구조체, Java같은 객체지향 언어라면 객체에 데이터 필드와 링크필드를 만듭니다. 보통 데이터 필드는 value라는 이름의 변수를 사용해 노드의 값을 저장하고, 링크 필드는 next 변수를 사용해 다음 노드의 포인터나 참조값을 저장해 노드와 노드를 연결합니다.

 

- Head

건물에 들어가려면 출입문을 찾아야 합니다. 리스트를 하나의 건물로 비유하자면 출입문에 해당하는 것이 head입니다. LinkedList를 사용하기 위해서는 이 head가 가리키고 있는 첫 번째 노드를 찾아야 합니다.

 

- Tail

가장 마지막 노드를 뜻합니다.

 

- Node노드는 데이터 값과 연결되어 있는 다음 노드에 대한 포인터를 가지고 있습니다.

 

 

LinkedList의 구현 (Java)

 

- toString() : LinkedList 안에 있는 노드들을 차례로 출력

- size() : LinkedList 안에 있는 노드의 개수를 리턴

- get(int index) : 특정 인덱스에 들어있는 값을 리턴

- indexOf(Object value) : 특정 값이 들어 있는지 head부터 확인 / 있으면 index를 없으면 -1을 리턴

- Node(Int index) : LinkedList에서 특정 인덱스의 노드를 리턴

 

* 삽입/삭제에 대한 설명은 생략하겠습니다.

 

 

자바로 작성한 LinkedList 코드는 다음과 같습니다.

package com.eunjin;

public class LinkedList {
	
	private Node head;
	private Node tail;
	private int size = 0;
	
	private class Node {
		private Object data;
		private Node next;
		
		public Node(Object input) {
			this.data = input;
			this.next = null;
		}
		
	}
	
	public String toString() { //string type 리턴
		String str;
		
		if(size==0) {
			return "[]";
			
		}
		else {
			Node x = head;
			str = "[";
			while(x.next!=null) {
				str += x.data + ",";
				x=x.next;
			}
			str += (x.data+"]");
		}
		
		return str;
	}
	
	public int size() {
		return size;
	}
	
	public Object get(int index) {
		Node x = node(index);
		return x.data;
	}
	
	public int indexOf(Object value) { //특정 데이터가 존재하는지 확인
		Node temp = head;
		int index = 0;
		while(temp.data!=value) {
			if(temp.next==null) {
				return -1;
			}
			index++;
		}
		return index;
	}
	public void addFirst(Object input) {
		Node newNode = new Node(input);
		newNode.next = head;
		head = newNode;
		size++;
		
		if(head.next==null) {
			tail=head;
		}
	}
	
	public void addLast(Object input) {
		if(size==0) {
			addFirst(input);
		}
		else {
			Node newNode = new Node(input);
			tail.next=newNode;
			tail=newNode;	
			size++;
		}
	}
	
	Node node(int index) {//특정 인덱스의 노드 알아내기
		Node x=head;
		for(int i=0;i<index;i++) {
			x=x.next;
		}
		return x;
	}
	
	public void add(int index, Object input) {
		
		Node newNode = new Node(input);
		
		if(index==0) {
			addFirst(input);
		}
		else {
			Node temp1 = node(index-1);
			Node temp2 = temp1.next;
			
			temp1.next=newNode;
			newNode.next=temp2;
			size++;
			
			if(newNode.next==null) { //새로운 노드의 다음이 없다면
				tail=newNode;
			}
		}
	}
	
	public Object removeFirst() { //첫번째 데이터 삭제 후 삭제된 data를 리턴함
		
		Node temp = head;
		head = temp.next;
		
		Object removedData = temp.data;
		temp=null;
		size--;
		
		return removedData;
	}
	
	public Object remove(int index) {
		if(index==0) {
			return removeFirst();
		}
		else if(index == size-1) {
			Node temp = node(index-1);
			Object removedData = temp.next.data;
			temp.next=null;
			tail=temp;
			return removedData;
		}
		else {
			Node temp = node(index-1);
			
			Object removedData = temp.next.data;
			temp.next.data=null;
			
			temp.next=temp.next.next;
			
			if(temp.next.next==tail) {
				tail=temp;
			}
			size--;
			
			return removedData;
		}
	}
	
	public Object removeLast() {
		return remove(size-1);
	}
	
	
	public static void main(String[] args) {
		LinkedList test = new LinkedList();
		
		test.add(0,1);
		test.add(1,2);
		test.add(2,3); //[1,2,3]
		
		test.addFirst(4); //[4,1,2,3]
		test.addLast(5); //[4,1,2,3,5]
		
		System.out.println(test.removeFirst());//-> 4 [1,2,3,5]
		System.out.println(test.remove(1));//-> 2 [1,3,5]
		System.out.println(test.removeLast());//-> 5 [1,3]
		
		System.out.println(test.toString());
		
	}

}