Linked List

Question 1

What is a List Node?

Answer 1

public class LinkNode {
	public int value; 
	public LinkNode next;

	public LinkNode (int value)
	{
		this.value = value;
	}
}

Question 2

How to count the size of a linked list?

Answer 2

int size()
	{
		int count = 0;
		if (head == null) return 0;
		LinkNode tmp = head;
		while (tmp != null)
		{
			count++;
			tmp = tmp.next;
		}
		return count;
	}

Question 3

How to check the value at an index?

Answer 3

int valueAt(int index)
	{
		if (head == null) return Integer.MAX_VALUE;
		LinkNode tmp = head;
		int count = 0;
		while (tmp != null)
		{
			tmp = tmp.next;
			count++;
			if (count == index)
				return tmp.value;
		}
		return Integer.MAX_VALUE;
	}

Question 4

How to do pushBack?

Answer 4

void pushBack(int val)
	{
		LinkNode tmp = head;
		if (head == null)
		{
			head = new LinkNode (val);
			return;
		}
		while(true)
		{
			if (tmp.next == null)
			{
				tmp.next = new LinkNode(val);
				return;
			}
			tmp = tmp.next;
		}
	}

Question 5

How to pushFront?

Answer 5

void pushFront(int val)
	{
		if (head == null)
		{
			head = new LinkNode (val);
			return;
		}
		LinkNode tmp = new LinkNode (val);
		tmp.next = head;
		head = tmp;
	}

Question 6

How to insert at a specific index?

Answer 6

void insert(int index, int val)
	{
		if (head == null) return;
		if (index == 0)
		{
			this.pushFront(val);
			return;
		}
		LinkNode tmp = head;
		int count = 0;
		while (tmp != null)
		{
			if (tmp.next == null && index == count)
			{
				this.pushBack(val);
			}
			if (count == index-1)
			{
				LinkNode tmp2 = tmp.next;
				tmp.next = new LinkNode (val);
				tmp.next.next = tmp2;
				return;

			}
			count++;
			tmp = tmp.next;
		}
	}

Question 7

How to erase a node at an index?

Answer 7

void erase(int index)
	{
		if (head == null) return;
		LinkNode tmp = head;
		int count = 0;
		while (tmp != null)
		{
			count++;
			if (count == index)
			{
				tmp.next = tmp.next.next;
			}
			tmp = tmp.next;
		}
	}

Question 8

How to print value from n to End?

Answer 8

int valueFromNtoEnd(int n)
	{
		int value = Integer.MAX_VALUE;
		LinkNode tmp = head;
		LinkNode runner = head;
		int count = 0;
		while (tmp != null)
		{
			while (runner.next != null)
			{
				count++;
				if (count > n)
				{		
					break;
				}
				runner = runner.next;
			}
			if (count == n)
				return tmp.value;
			tmp = tmp.next;
			runner = tmp;
			count =0;
		}
		return Integer.MAX_VALUE;

}

Question 9

How to reverse a linked list?

Answer 9

void reverse()
	{
		LinkNode curr = head;
		LinkNode prev = null;
		LinkNode next = null;

		while (curr != null)
		{			
			next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		head = prev;

}

Question 10

How to remove a value?

Answer 10

void removeValue(int val)
	{
		LinkNode tmp = head;
		LinkNode prev = null;
		if (head == null) return;
		if (head.value == val)
			{
			head = head.next;
			return;
			}
		while (tmp!= null)
		{
			if (tmp.value == val)
			{
				prev.next = tmp.next;
			}
			prev= tmp;
			tmp = tmp.next;
		}
	}

Question 11

What is the time complexity for:
Lookup, search, insert, delete?
What is space complexity?

Answer 11

Lookup: O(n)
search: O(n)
insert: O(1)
delete: O(1)
Space: O(n)