java 简单链表实现

1）链表：链表是java中数据结构之一，在内存中是一块不连续的内存空间，彼此之间的数据连接关系是一个对象持有下一个对象的引用。链表的插入方式可简单分为从链表头部插入和从尾部插入，其中从头部插入较为简单。下面分别通过代码实现：

 

2）从头部插入代码：

package com.zt.link;

import java.util.NoSuchElementException;

public class LinkTest {
	private Node first;//链表头元素
	private int size;//链表大小
	public static void main(String[] args) {
		LinkTest link = new LinkTest();
		link.addFirst("结点1");
		link.addFirst("结点2");
		link.addFirst("结点3");
		
		System.out.println(link.size);
		link.deleteFirst();
		link.display();
	}
	//在链表头部添加结点
	public boolean addFirst(Object value){
		Node newNode = new Node(value, null);
		if(first == null)//判断是否为第一个结点，若是直接把新节点赋值给第一个结点
			first = newNode;
		else {
			newNode.next = first;//若不是第一个结点，新节点作为第一个结点
			first = newNode;
		}
		size ++;
		return true;
	}
	//在链表头部删除结点
	public Node deleteFirst() {
		if(first == null)
			throw new NoSuchElementException();
		Node temp = first;
		first = first.next;
		size --;
		return temp;
	}
	
	//获取指定位置的元素
	public Node get(int index) {
		if(index < 0 ||index > size)
			throw new IllegalArgumentException();
		Node cur = first;
		int count = 0;
		while(cur != null) {
			if(count ++ == index)
				return cur;
			else {
				cur = cur.next;
			}
		}
		return null;
	}
	//遍历链表
	public void display() {
		Node cur = first;
		while(cur != null){
			System.out.println(cur.value);
			cur = cur.next;
		}
	}
}
class Node {
	Object value;//为了方便取值，没有加权限修饰符
	Node next;
	public Node(Object value,Node next) {
		this.value = value;
		this.next = next;
	}
}

  从尾部插入代码，为了插入方便多添加一个last结点：

package com.zt.link;

import java.util.NoSuchElementException;

public class LinkTest {
	private Node first;//链表头元素
	private Node last;//链表尾元素
	private int size;//链表大小
	public static void main(String[] args) {
		LinkTest link = new LinkTest();
		link.addLast("结点1");
		link.addLast("结点2");
		link.addLast("结点3");
		link.deleteLast();
		System.out.println(link.get(1).value);
		link.display();
	}
	
	//在链表尾部添加结点
	public boolean addLast(Object value) {
		Node newNode = new Node(value, null);
		if(first == null)//判断是否为第一个结点，若是第一个结点和尾结点指向新结点
			first = last = newNode;
		else {
			last.next = newNode;
			last = newNode;
		}
		size ++;
		return true;
	}
	//移除尾元素
	public Node deleteLast() {
		if(first == null)//判断链表是否为空
			throw new NoSuchElementException();
		Node cur = first;//cur表示当前遍历结点
		Node prev = null;//prev当前结点的上一个结点
		while(cur != null) {
			if(cur == last) {
				Node temp = last;
				last = prev;
				last.next = null;
				size --;
				return temp;
			} else {
				prev = cur;
				cur = cur.next;
			}
		}
		return null;
	}
	//获取指定位置的元素，和从头部插入一样
	public Node get(int index) {
		if(index < 0 ||index > size)
			throw new IllegalArgumentException();
		Node cur = first;
		int count = 0;
		while(cur != null) {
			if(count ++ == index)
				return cur;
			else {
				cur = cur.next;
			}
		}
		return null;
	}
	//遍历链表，和从头部插入一样
	public void display() {
		Node cur = first;
		while(cur != null){
			System.out.println(cur.value);
			cur = cur.next;
		}
	}
}
class Node {
	Object value;//为了方便取值，没有加权限修饰符
	Node next;
	public Node(Object value,Node next) {
		this.value = value;
		this.next = next;
	}
}