数据结构之单链表的定义以及实现

单链表的定义:

单链表是一种链式存取的数据结构,链表中的数据是以结点来表示的,每个结点的构成:元素(存储的数据)+ 指针(指向后继节点)

单链表的操作:

删除节点 public E remove(int index)

添加节点 public void add(int index,E e)

链表是否空 public boolean isEmpty()

获取链表对应索引元素 public E get(int index)

获取单链表大小 public int getSize()

链表是否存在当前元素 public Boolean contains(E e)

内部结构:


链表的应用:

如果需要频繁的对数据进行增删 链表效率会高于数组 因为数组插入要对其后所有元素后移一位

实现代码:

package demo;
 
public class LinkedList<E> {
 
//	成员内部类
	private class Node {
		E e;
		Node next;
 
//      节点 构造方法的重构
		public Node(E e, Node next) {
			this.e = e;
			this.next = next;
		}
 
		public Node(E e) {
			this(e, null);
		}
 
		public Node() {
			this(null, null);
		}
 
//		重写 toString 方法
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return e.toString();
		}
	}
 
//  此处用的是虚拟头节点 会浪费一个空间
	private Node dummyHead;
	private int size;
 
	public LinkedList() {
		this.size = 0;
//		此处相当于为虚拟头节点 申请空间
//		用虚拟头节点 缺点是浪费一个空间 但是 查询插入删除等操作会非常方便
//		注意dummyHead = null  和 dummyHead = new Node(null,null) 是两个概念
		this.dummyHead = new Node(null, null);
	}
 
//	获取链表当前的大小
	public int getSize() {
		return size;
	}
 
//	链表是否为空	
	public Boolean IsEmpty() {
		return size == 0;
	}
 
//  在指定位置处添加节点
	public void add(int index, E e) {
//      此处要新建一个 Node 来寻找带插入位置
//		如果直接用dummyHead 会改变dummyHead 的位置
//		这样下次再操作 头就丢了整个链表就乱了 所以dummyHead 只负责指向头节点
		Node prev = dummyHead;
		if (index < 0 || index > size) {
			System.out.println("非法操作");
 
		} else {
			for (int i = 0; i < index; i++) {
				prev = prev.next;
 
			}
			Node node = new Node(e);
			node.next = prev.next;
			prev.next = node;
			size++;
		}
	}
//	获取当前索引对应的节点
	public E get(int index) {
		if (index < 0 || index > size) {
		     System.out.println("非法操作");
		     return null;
		}else {
			Node prev  = dummyHead;
			for (int i = 0; i < index; i++) {
				prev =prev.next;
			}
			return prev.e;
		}
		
	}
//   链表是否存在当前节点
	public Boolean contains(E e) {
		Node prev = dummyHead.next;
		for (; prev !=null; prev =prev.next) {
			if (prev.e.equals(e)) {
				return true;
			}
			
		}
		return false;
		
	}
//	删除当前位置元素
	public E  remove(int index) {
		if (index <0 || index >size) {
			System.out.println("非法操作");
			return null;
		}else {
			Node prev = dummyHead;
			for (int i = 0; i < index; i++) {
				prev =prev.next;
			}
			Node node =prev.next;
			prev.next = node.next;
			node.next= null;
			size--;
			return node.e;
		}
		
	}
	@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			Node prve = dummyHead.next;
			for (; prve != null ; prve =prve.next) {
				sb.append(prve +"->");
						
			}
			sb.append("NULL");
			return sb.toString();
		}
 
}

测试代码:

package demo;
 
public class Test {
	public static void main(String[] args) {
		LinkedList linkedList  = new LinkedList();
		for (int i = 0; i <10; i++) {
			 linkedList.add(i, i);
		}
		System.out.println(linkedList);
		System.out.println(linkedList.contains(2));
		linkedList.add(2, 100);
		System.out.println(linkedList);
		System.out.println(linkedList.remove(2));
 
		System.out.println(linkedList);
	}
 
}

 

© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发