java实现单链表操作

2018-02-27 11:49:27来源:oschina作者:大灰狼时间人点击

分享


单链表的存储结构如图:每一个结点都分为数据域和指针域两部分,其中head为头结点,头结点的数据域可以不存放任何数据,而指针域存放的是指向链表第一个结点的地址。


每一个结点的指针域都指向下一个结点的地址,最后一个结点的指针为null。


关于头指针和头结点:


① 头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前(头结点并不是链表的必须要素)。


② 头指针是指向链表第一个结点的指针(若链表有头结点,当然是指向头结点),具有标识作用,无论链表是否为空,头指针均不为空,且不能随意改动(就像风筝断了线的话就找不回来了)。


参考:https://www.jianshu.com/p/2a0db725044c

实现过程:


1、创建一个类Node.java:


package com.list.singlyLinkedList;
public class Node {
public Node next;
public int value;
public Node() {
next = null;
}
public Node(int v) {
value = v;
}
}

2、新建接口ISinglyLinkedList.java并定义基本的方法:


package com.list.singlyLinkedList;
public interface ISinglyLinkedList {
/**
* 在链表前添加结点(头插法)
* @param val
*/
public void addPre(int val);

/**
* 链表尾部添加结点(尾插法)
* @param val
*/
public void append(int val);

/**
* 删除指定位置的结点
* @param pos 索引从0开始
* @return
*/
public Node deletepos(int pos);

/**
* 根据索引获取结点
* @param pos
* @return
*/
public Node getElem(int pos);

/**
* 输出链表
*/
public void print();
}

3、新建SinglyLinkedList类实现接口中的方法:


package com.list.singlyLinkedList;
public class SinglyLinkedList implements ISinglyLinkedList {
private Node head;
public SinglyLinkedList() {
head = null;
}
@Override
public void addPre(int val) {
Node n = new Node(val);
if (head == null) {
head = n;
} else {
n.next = head;
head = n;
}
}
@Override
public void append(int val) {
Node n = new Node(val);
Node current = head;

if (current == null) {
head = n;
return;
}
while (current != null) {
if (current.next == null) {
current.next = n;
return;
}
current = current.next;
}
}
@Override
public Node deletepos(int pos) {
Node current = head;
int counter = 0;
if (pos == 0) {
head = head.next;
return current;
}
while (current != null) {
if ((counter == (pos - 1)) && (current.next != null)) {
Node temp = current.next;
current.next = temp.next;
return temp;
}
current = current.next;
counter++;
}
return null;
}

@Override
public Node getElem(int pos) {
Node current = head;
int counter = 0;
if (pos == 0) {
return current;
}
while (current != null) {
if ((counter == (pos - 1)) && (current.next != null)) {
Node temp = current.next;
return temp;
}
if (current.next != null)
current = current.next;
else
break;
counter++;
}
return null;
}
@Override
public void print() {
Node current = head;
while (current != null) {
System.out.println(current.value);
current = current.next;
}
}
public static void main(String[] args) {
SinglyLinkedList l = new SinglyLinkedList();
//l.addpre(2);
//l.addpre(1);
l.append(5);
l.append(6);
l.deletepos(0);
l.append(10);
l.addPre(1);

l.print();
System.err.println("-----------");
System.err.println(l.getElem(0));
}
}

新手如有错误,请不吝指正,谢谢。

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台