Java实现线性表和单链表以及链表的合并

java实现线性链表

 

package list;

public class LineList {
	Object[] elem;
	int current;
	int size;

	public LineList() {
		this(100);//初始化生成一个100个元素的数组
	}

	public LineList(int a) {
		elem = new Object[a];
		size = a;
		current = 0;
	}

        //方法用来判断数组大小是否还够用
	public void enhanceSize() {
		if (current == size) {
			size+=10;
			Object[] newElem = new Object[size];
			int n=0;
		     for(Object obj:elem){
		    	 newElem[n]=obj;
		    	 n++;
		     }
			elem = newElem;
		}

	}

   //添加元素
	public void add(Object e){
		enhanceSize();
		elem[current]=e;
		current++;
		
	}

// 获取元素
	public Object get(int index){
		
		return elem[index];
		
	}

}

 

 

单链表;

1)节点定义：

package linekedList;

public class NodeDemo {
	int data;
	NodeDemo next;

}

 2）单链表;

 

package linekedList;

public class LinkedListDemo {
	NodeDemo head = new NodeDemo();
	NodeDemo currentNode = head;

//尾插法添加元素
	public void add(int e) {
		NodeDemo newNode = new NodeDemo();
		newNode.data = e;
		currentNode.next = newNode;
		currentNode = newNode;

	}

获得指定序号的元素
	public Object get(int index) {
		int i = 0;
		NodeDemo nodep = head;
		while ((nodep.next != null) && i < index) {
			nodep = nodep.next;
			i++;

		}
		return nodep.data;
	}


//链表的插入
	public void insertList(int index, int e) {

		if (index <= 0) {
			System.out.println("插入位置不合法！！！");
		} else {
			NodeDemo newNode = new NodeDemo();
			newNode.data = e;

			int i = 0;
			NodeDemo nodep = head;
			while ((nodep.next != null) && i < index) {
				nodep = nodep.next;
				i++;

			}
			newNode.next = nodep.next;
			nodep.next = newNode;
		}

	}
	

//两个有序链表的合并，合并后为一个有序链表
	public LinkedListDemo mergeLinkedList(LinkedListDemo lB) {
		NodeDemo lANode = this.head.next;
		NodeDemo lBNode = lB.head.next;
		LinkedListDemo lC = new LinkedListDemo();
		NodeDemo currentNode = lC.head;
		while (lANode != null && lBNode != null) {
			if (lANode.data <= lBNode.data) {
				currentNode.next = lANode;
				currentNode = lANode;
				lANode = lANode.next;
				System.out.println("A的");

			} else {
				currentNode.next = lBNode;
				currentNode = lBNode;
				lBNode = lBNode.next;
				System.out.println("B的");
			}

		}
		if (lANode != null) {
			currentNode.next = lANode;
		} else {
			currentNode.next = lBNode;

		}
		return lC;

	}
	

}