Data structure and algorithm 17 table insertion sorting

Table insert sort

Randomly generate a set of numbers, sort them through the linked list, and then copy them to the array to improve efficiency

class Link
{
	public long  ddata;
	public Link next;
	public Link(long dd)
	{
		ddata = dd;
	}
	public void displayLink()
	{
		System.out.println(ddata + " ");
		
	}
}
class SortedList
{
	private Link first;
	public SortedList()
	{
		first = null;
	}
	public SortedList(Link[] linkArr)
	{
		first = null;
		for(int j=0;j<linkArr.length;j++)
		insert(linkArr[j]);
	}
	public boolean Empty()
	{
		return (first == null);
	}
	public void insert(Link k)
	{
		
		Link previous = null;
		Link current = first;
		while(current !=null&&k.ddata>current.ddata)
		{
			previous = current;
			current = current.next;
		}
		if(previous == null)
		
			first = k;
		else
			previous.next =k;
			k.next = current;
		
	}
	public Link remove()
	{
		Link temp = first;
		first = first.next;
		return temp;
	}
	public void displayList()
	{
		System.out.println("link");
		Link currrent = first;
		while(currrent != null)
		{
			currrent.displayLink();
			currrent = currrent.next;
		}
		System.out.println(" ");
	}
}
class ListInsertionApp
{
	public static void main(String[] args)
	{
		int size = 10;
		Link[] linkArray = new Link[size];
		for(int j=0;j<size;j++)
		{
			int n = (int)(java.lang.Math.random()*99);
			Link newLink = new Link(n);
			linkArray[j] = newLink;
		}
		System.out.println("unsorted");
		for(int j=0;j<size;j++)
		{
			System.out.print(linkArray[j].ddata+" ");
			System.out.println(" ");
			SortedList theSortedList = new SortedList(linkArray);
			for(int i=0;i<size;i++)
				linkArray[i] = theSortedList.remove();
			System.out.print("sorted");
			for(int x=0;x<size;x++)
			System.out.print(linkArray[x].ddata+" ");
			System.out.println(" ");
		}
	}
}

Bidirectional linked list: allow forward traversal and backward traversal

Disadvantages: each time you insert or delete a chain node, you need to refer to four chain nodes instead of two.

The following is the insertion function, which is divided into insertion from the chain header and insertion from the chain tail

class Link
{
	public long ddata;
	public Link next;
	public Link previous;
	public Link(long d)
	{
		ddata = d;
	}
	public void displayLink()
	{
		System.out.println(ddata + " ");
	}
}
class DoublyLinkedList
{
	private Link first;
	private Link last;
	public DoublyLinkedList()
	{
		first = null;
		last = null;
	}
	public boolean isEmpty()
	{
		return first == null;
	}
	public void insertFirst(long dd)
	{
		Link newLink = new Link(dd);
		if(isEmpty())
			last = newLink;
		else
			first.previous = newLink;
		newLink.next = first;
		first = newLink;
		
	}
	public void insertLast(long dd)
	{
		Link newLink = new Link(dd);
		if(isEmpty())
			first = newLink;
		else
		{
			last.next = newLink;
			newLink.previous = last;			
		}
		last = newLink;
	}
}

Tags: Java

Posted on Thu, 09 Jan 2020 11:04:26 -0800 by alexu'