链表-Java实现链表数据结构
链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上 一个/或下一个节点的位置的链接(“links”)
链表(Linked list):是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数 据,而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针
域,空间开销比较大。
单向链表
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息,另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单向链表只可向一个方向遍历,一般查找一个节点的时候需要从第一个节点开始每次访问下一个节 点,一直访问到需要的位置。而插入一个节点,对于单向链表,我们只提供在链表头插入,只需要将当 前插入的节点设置为头节点,next指向原头节点即可。删除一个节点,我们将该节点的上一个节点的 next指向该节点的下一个节点
在表头增加节点:
在表头删除节点:
/**
* @author shihaowei
* @date 2020-06-03 16:28
*/
public class SingleLinkList {
private int size;
private Node head;
public SingleLinkList() {
this.size = 0;
this.head = null;
}
/** 内部类节点 */
public class Node {
private Object data;
private Node next;
public Node(Object data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + next +
'}';
}
}
/** 添加节点 */
public Object addHead(Object obj){
Node newNode = new Node(obj);
if (size == 0){
head = newNode;
}else {
newNode.next = head;
head = newNode;
}
size++;
return obj;
}
/** 删除头节点 */
public Object delHead(){
if (size > 0){
Object data = head.data;
head = head.next;
size--;
return data;
}
return false;
}
/** 获取指定数据节点*/
public Node find(Object value){
Node current = head;
int tempsize = size;
while (tempsize>0){
if (current.data.equals(value)){
return current;
}else {
current = current.next;
tempsize--;
}
}
return null;
}
/** 删除数据节点*/
public boolean delValue(Object value){
if (size == 0){
return false;
}
Node current = head;
Node prenode = head;
while (!current.data.equals(value)){
if (current.next == null){
return false;
}else {
prenode = current;
current = current.next;
}
}
//如果第一个节点就是要删除的
if (current == head){
head = current.next;
size--;
}else {
prenode.next = current.next;
size--;
}
return true;
}
@Override
public String toString() {
return "SingleLinkList{" +
"size=" + size +
", head=" + head +
'}';
}
public static void main(String[] args) {
SingleLinkList linkList = new SingleLinkList();
linkList.addHead("a");
linkList.addHead("b");
linkList.addHead("c");
//linkList.delHead();
System.out.println(linkList);
}
}
双端链表
对于单项链表,我们如果想在尾部添加一个节点,那么必须从头部一直遍历到尾部,找到尾节点,然后在尾节点后面插入一个节点。这样操作很麻烦,如果我们在设计链表的时候多个对尾节点的引用,那么会简单很多。
public class DoublePointLinklist {
private Node head;
private Node tail;
private int size;
// 链表的节点类
private class Node{
private Object data;
private Node next;
public Node(Object data) {
this.data = data;
}
}
public DoublePointLinklist() {
this.head = null;
this.tail = null;
this.size = 0;
}
/**
* 头节点插入
* @param data
* @return
*/
public Object addHead(Object data){
Node node = new Node(data);
if (head.next == null){
head = node;
tail = node;
}else {
head.next = head;
head = node;
}
size++;
return data;
}
/**
* 尾节点插入
* @param data
* @return
*/
public Object addTail(Object data){
Node node = new Node(data);
if (head.next == null) {
head = node;
tail = node;
}else {
tail.next = tail;
tail = node;
}
size++;
return data;
}
/**
* 删除节点
* @param data
* @return
*/
public boolean delNode(Object data){
if ( size == 0){
return false;
}
Node prenode = head;
Node current = head;
while (!head.data.equals(data)){
if (current.next == null){
return false;
}else {
prenode = current;
current = current.next;
}
}
if (current == head){
head = current.next;
}else {
prenode.next = current.next;
}
size--;
return true;
}
}
双向链表
我们知道单向链表只能从一个方向遍历,那么双向链表它可以从两个方向遍历
package person.shw.datastructure.link;
/**
* @author shihaowei
* @date 2020-06-08 16:39
*/
public class TwoWayLinkedList {
private Node head;
private Node tail;
private int size;
/**
* 节点类
*/
private class Node{
private Object object;
private Node next;
private Node pre;
public Node(Object object) {
this.object = object;
}
}
public TwoWayLinkedList() {
size = 0;
head = null;
tail = null;
}
/**
* 链表头增加节点
* @param obj
*/
public void addHead(Object obj){
Node node = new Node(obj);
if (size == 0){
head = node;
tail = node;
}else {
head.pre = node;
head.next = head;
head = node;
}
size++;
}
/**
* 链表尾添加节点
* @param obj
*/
public void addTail(Object obj){
Node node = new Node(obj);
if (size == 0) {
head = node;
tail = node;
}else {
tail.next = node;
node.pre = tail;
tail = node;
}
size++;
}
/**
* 删除头节点
* @return
*/
public Object deleteHead(){
Node temp = head;
if (size != 0){
head = head.next;
head.pre = null;
size --;
}
return temp;
}
/**
* 删除尾节点
* @return
*/
public Object deleteTail(){
Node temp = tail;
if (size != 0){
tail = tail.pre;
size --;
}
return temp;
}
/**
* 获取节点个数
* @return
*/
public int getSize(){
return size;
}
/**
* 显示节点信息
*/
public void display(){
if(size >0){
Node node = head;
int tempSize = size;
if(tempSize == 1){
//当前链表只有一个节点
System.out.println("["+node.object+"]");
return; }
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.object+"->");
}else if(node.next == null){
System.out.print(node.object+"]");
}else{
System.out.print(node.object+"->");
}
node = node.next;
tempSize--;
}
System.out.println(); }else{
//如果链表一个节点都没有,直接打印[]
System.out.println("[]");
}
}
}
有序链表
前面的链表实现插入数据都是无序的,在有些应用中需要链表中的数据有序,这称为有序链表。
在有序链表中,数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动),另外链表可以扩展到全部有效的使用内存,而数组只能局限于一个固定的大小中。
public class OrderLinkedList {
private Node head;
private class Node{
private int data;
private Node next;
public Node(int data){
this.data = data;
}
}
public OrderLinkedList(){
head = null;
}
//插入节点,并按照从小打到的顺序排列 public void insert(int value){
Node node = new Node(value);
Node pre = null;
Node current = head;
while(current != null && value > current.data){
pre = current;
current = current.next;
}
if(pre == null){
head = node;
head.next = current;
}else{
pre.next = node;
node.next = current;
}
}
//删除头节点
public void deleteHead(){
head = head.next;
}
public void display(){
Node current = head;
while(current != null){
System.out.print(current.data+" ");
current = current.next;
}
System.out.println("");
}
}
在有序链表中插入和删除某一项最多需要O(N)次比较,平均需要O(N/2)次,因为必须沿着链表上一 步一步走才能找到正确的插入位置,然而可以最快速度删除最值,因为只需要删除表头即可,如果一个 应用需要频繁的存取最小值,且不需要快速的插入,那么有序链表是一个比较好的选择方案。比如优先 级队列可以使用有序链表来实现
总结
上面我们讲了各种链表,每个链表都包括一个LinikedList对象和许多Node对象,LinkedList对象通常 包含头和尾节点的引用,分别指向链表的第一个节点和最后一个节点。而每个节点对象通常包含数据部 分data,以及对上一个节点的引用prev和下一个节点的引用next,只有下一个节点的引用称为单向链 表,两个都有的称为双向链表。next值为null则说明是链表的结尾,如果想找到某个节点,我们必须从 第一个节点开始遍历,不断通过next找到下一个节点,直到找到所需要的。栈和队列都是ADT,可以用 数组来实现,也可以用链表实现
还没有评论,来说两句吧...