[Java] Linked List 개념 / 구현

Linkedlist란

- 데이터와 다음데이터를 가리키고 있는 포인터로 이루어져 있는 노드가 연결되어 있는 자료구조 형태를 의미한다.

- 데이터의 삽입, 삭제가 쉽다 (배열의 경우 삽입, 삭제를 할 때 index를 모두 옮겨야함)

- 데이터 탐색에 시간이 걸림 (index가 없기 때문)

 

 

- 자바에서는 링크리스트를 제공해주고, get(index)의 형태로 index도 제공해준다.

- 이중링크드리스트(앞뒤로 포인터가 있음), 원형연결리스트도 있다.

 

-  구현한 링크드리스트 (개념확인용/ 스터디에서 주어진 메소드로 수정예정)

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() {
			return String.valueOf(this.data);
		}
	}
	public void addFirst(Object input) {
		Node newNode = new Node(input);
		newNode.next = head; //또다른 값이 addFirst를 할때 기존꺼를 밀어내고 들어가야함
		head = newNode; //리스트의 헤드값이 이것이다 지정
		size++;

		if(head.next == null) { //다음노드가 존재하지 않는다면
			tail = head;
		}
	}
	public void addLast(Object input) {
		Node newNode = new Node(input);
		if(size == 0) {
			addFirst(input); // 데이터가 아예 없는 상태면 노상관
		}else {
			tail.next = newNode;
			tail = newNode;
			size++;
		}
	}
	public void add(int i,Object input) {
		if(i == 0) {
			addFirst(input);
		}else {
			Node prev = getnode(i-1); //그 전 변수를 알면 next를 통해 그자리에 있는 노드 접근 가능
			Node after = prev.next;
			Node newNode = new Node(input);
			
			prev.next = newNode;
			newNode.next = after;
			size++;
			if(newNode.next == null) { //tail도 야무지게 챙겨서 줘야지!
				tail = newNode;
			}	
		}
	}
	public Object removeFirst() { //자바규칙: 삭제한 데이터 리턴하기
		Node temp = head;
		head = head.next;
		Object returndata = temp.data;
		temp = null;
		size--;
		return returndata;
	}
	public Object remove(int i) {
		if(i == 0) {
			return removeFirst();
		}
		
		Node prev = getnode(i-1); //이전노드를 알아야한다
		Node now = prev.next;
		prev.next = prev.next.next;
		
		Object returndata = now.data;
		
		if(now == tail) { //삭제하는게 tail이면
			tail = prev;
		}
		now = null; // 안써줘도됨
		size--;	
		
		return returndata;
		
	}
	public Object removeLast() {
		return remove(size-1);
	}
	public Node getnode(int index) {
		Node x = head;
		for(int i=0;i<index;i++) {
			x = x.next;
		}
		return x;
	}
	public String toString() {
		if(head == null) {
			return "[]";
		}
		Node temp = head;
		String str = "[";
		
		while(temp.next !=null) {
			str += temp.data + ",";
			temp = temp.next;
		}
		str += temp.data; // 마지막은 수동으로
		
		return str;
	}
	public int size() {
		return size;
	}
	public Object get(int i) { //data값 가져오기
		Node temp = getnode(i);
		return temp.data;
	}
	public int indexof(Object data) { //특정 값이 어떤 index값에 위치하는가
		Node temp = head;
		int index = 0;
		while(temp.data != data) {
			temp = temp.next;
			index++;
			if(temp == null) {// 끝까지 갔는데도 없을 경우
				return -1;
			}
		}
		return index;
	}
	
}

 

출처:  생활코딩
https://www.youtube.com/playlist?list=PLuHgQVnccGMDsWOOn_P0EmAWB8DArS3Fk