`
hello_world_hello
  • 浏览: 8372 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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;
	}
}

 

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics