[자료 구조] LinkedList 개념 설명과 구현

⬛ LinkedList 개념

 

• 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조로 다음 노드에 대한 참조를 통해 연결된다.
• 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성된다.
• 동적으로 메모리를 사용할 수 있기 때문에 메모리를 효율적으로 사용할 수 있다.
• 삭제와 삽입의 과정만은 O(1)으로 해결되지만 해당 위치를 찾기 위해 첫 번째 노드부터 순차적으로 요소에 접근하는 과정에서 O(n)의 시간이 추가적으로 발생한다. 결국 O(n)의 시간복잡도를 가지게 된다.

⬛ LinkedList 연산

1.  add(E e) : list의 끝에 지정된 요소를 추가

2. add(int index, E element) : list의 지정된 위치에 지정된 요소 삽입

3. addFirst(E e) : list의 시작 부분에 지정된 요소 삽입

4. get(int index) : list의 지정된 위치에 있는 요소를 반환

5. remove(int index) : list의 지정된 위치에 있는 요소를 제거

6. set(int index, E element) : list의 지정된 위치에 있는 요소를 지정된 요소로 바꾸기 
7. clear() : list의 모든 요소를 제거

8. size() : list의 요소 수를 반환

⬛ LinkedList 구현

MyLinkedList.java

MyLinkedList.java

package com.LinkedList;

public class MyLinkedList{

	private Node head = new Node();
	private Node tail;
	private int size = 0;

	// Appends the specified element to the end of this list.
	private void add(int data){
		if (size == 0) {
			Node new_node = new Node(data);
			head.next = new_node;
			tail = new_node;
			size++;
			return;
		}
		Node new_node = new Node(data);
		tail.next = new_node;
		tail = new_node;
		size++;
	}

	// Inserts the specified element at the specified position in this list.
	private void add(int index, int data){
		if (index == 0) {
			addFirst(data);
			return;
		}
		Node new_node = new Node(data);
		Node pre_node = node(index - 1);
		new_node.next = pre_node.next;
		pre_node.next = new_node;
		size++;
	}

	// Inserts the specified element at the beginning of this list.
	private void addFirst(int data){
		Node new_node = new Node(data);
		new_node.next = head.next;
		head.next = new_node;
		size++;
	}

	private Node node(int index){
		Node search = head;
		for (int i = 0; i <= index; i++) {
			search = search.next;
		}
		return search;
	}

	// returns the element at the specified position in this list.
	private int get(int index){
		return node(index).data;
	}

	// Removes the element at the specified position in this list.
	private void remove(int index){
		Node pre_node = node(index - 1);
		Node cur_node = node(index);
		Node next_node;
		if (index == size - 1) {
			tail = pre_node;
			pre_node = node(index - 1);
			pre_node.next = null;
			size--;
			return;
		}
		next_node = node(index + 1);
		pre_node.next = next_node;
		cur_node = null;
		size--;
	}

	// Replaces the element at the specified position in this list with the specified elements.
	private void set(int index, int data){
		node(index).data = data;
	}

	// Removes all of the elements from this list.
	private void clear(){
		int curSize = size();
		for (int i = 0; i < curSize; i++) {
			remove(0);
		}
	}

	// returns the number of elements in this list.
	private int size(){
		return size;
	}

	@Override
	public String toString(){
		if (size == 0) {
			return "[]";
		}
		String str = "[";
		Node search = head.next;
		while (search.next != null) {
			str += search.data + ", ";
			search = search.next;
		}
		str += search.data + "]";
		return str;
	}

	public static void main(String[] args){
		MyLinkedList list = new MyLinkedList();
		list.add(0);
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		System.out.println(list);
		list.add(1, 5);
		System.out.println(list);
		list.addFirst(6);
		System.out.println(list);
		list.remove(0);
		System.out.println(list);
		list.set(3, 9);
		System.out.println(list);
		System.out.println(list.get(2));
		System.out.println(list.size());
		list.clear();
		System.out.println(list);
		
	}
}

 

Node.java

Node.java

package com.LinkedList;

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