数据结构——线性表之链式存储结构

说故事的五公子

发布于 2019-09-11 17:22:29

5310

发布于 2019-09-11 17:22:29

单链表：

概念：

1、由于线性表的顺序存储在插入与删除时需要移动大量元素，适用于不经常改变元素的情况，那么当我们需要经常操作元素时该怎么办，这就有了接下来的线性表的链式存储结构 2、单链表在内存的存储位置不一定是一段连续的位置，它可以存放在内存中任何地方 3、单链表中除了用于存放数据的数据域外，还有存放指针的指针域，指针域的作用是指向链表的下一个节点（因为链表的元素在内存中的存放时任意位置的，所以需要指向下一个节点） 4、单链表第一个节点存储的位置叫做头指针，整个单链表的存取都是从头指针开始，单链表的最后一个节点是指针指向空（NULL）

单链表的操作：

  1 package com.alibaba.test03;
  2 
  3 import org.junit.jupiter.api.Test;
  4 
  5 
  6 /**
  7  * 1.  单链表的具体实现及操作
  8  * @author wydream
  9  *
 10  */
 11 
 12 public class SingLeLinkedList {
 13 
 14     private int size;//链表节点的个数
 15     private Node head;//头结点
 16     
 17     public SingLeLinkedList() {
 18         size=0;
 19         head=null;
 20     }
 21     
 22     //链表中的每个节点类
 23     private class Node{
 24         private Object data;//每个节点的数据
 25         private Node next;//每个节点指向下一个节点的连接
 26         
 27         public Node(Object data){
 28             this.data=data;
 29         }
 30     }
 31     
 32     //在表头添加元素
 33     public Object addHead(Object obj) {
 34         Node newHead=new Node(obj);
 35         
 36         if(size==0) {
 37             head=newHead;
 38         }else {
 39             newHead.next=head;
 40             head=newHead;
 41         }
 42         size++;
 43         return obj;
 44     }
 45     
 46     //在链表头删除元素
 47     public Object deleteHead() {
 48         Object obj=head.data;
 49         head=head.next;
 50         size--;
 51         return obj;
 52     }
 53     
 54     //查找指定元素，找到了返回元素Node，找不到返回Null
 55     public Node find(Object obj) {
 56         Node current=head;
 57         int tempSize=size;
 58         while(tempSize>0) {
 59             if(obj.equals(current.data)) {
 60                 return current;
 61             }else {
 62                 current=current.next;
 63             }
 64             tempSize--;
 65         }
 66         return null;
 67     }
 68     
 69     
 70     //删除指定的元素，删除成功则返回true
 71     public boolean delete(Object value) {
 72         
 73         if(size==0) {
 74             return false;
 75         }
 76         
 77         Node current=head;
 78         Node previous=head;
 79         while(current.data!=value) {
 80             if(current.next==null) {
 81                 return false;
 82             }else {
 83                 previous=current;
 84                 current=current.next;
 85             }
 86         }
 87         
 88         //如果删除的是第一个节点
 89         if(current==head) {
 90             head=current.next;
 91             size--;
 92         }else {//删除的不是第一个节点
 93             previous.next=current.next;
 94             size--;
 95         }
 96         return true;
 97     }
 98     
 99     //判断链表是否为空
100     public boolean isEmpty() {
101         return size==0;
102     }
103     
104     //显示节点信息
105     public void display() {
106         if(size>0) {
107             Node node=head;
108             int tempSize=size;
109             if(tempSize==1) {//当前链表只有一个节点
110                 System.out.println("["+node.data+"]");
111                 return;
112             }
113             while(tempSize>0) {
114                 if(node.equals(head)) {
115                     System.out.print("["+node.data+"->");
116                 }else if(node.next==null){
117                     System.out.print(node.data+"]");
118                 }else {
119                     System.out.print(node.data+"->");
120                 }
121                 node=node.next;
122                 tempSize--;
123             }
124             System.out.println();
125         }else {//如果链表一个节点都没有，直接打印
126             System.out.print("[]");
127         }
128     }
129     
130     @Test
131     public void test() {
132         SingLeLinkedList s=new SingLeLinkedList();
133         s.addHead("1");
134         s.addHead("2");
135         s.addHead("3");
136         s.addHead("4");
137         s.deleteHead();
138         s.display();
139     }
140     
141     
142     
143     
144 }

有序链表：

概念：

前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。
在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

有序链表的实现：

 1 /**
 2  * 
 3  * @author wydream
 4  *
 5  */
 6 
 7 public class OrderLinkedList {
 8     
 9     private Node head;
10 
11     private class Node{
12         private int data;
13         private Node next;
14         
15         public Node(int data) {
16             this.data=data;
17         }
18     }
19     
20     public OrderLinkedList() {
21         head=null;
22     }
23     
24     //插入节点，并按从小到大的顺序排列
25     public void insert(int value) {
26         Node node=new Node(value);
27         Node pre=null;
28         Node current=head;
29         while(current!=null&&value>current.data) {
30             pre=current;
31             current=current.next;
32         }
33         if(pre==null) {
34             head=node;
35             head.next=current;
36         }else {
37             pre.next=node;
38             node.next=current;
39         }
40     }
41     
42     //删除头节点
43     public void deleteHead() {
44         head=head.next;
45     }
46     
47     public void display() {
48         Node current=head;
49         while(current!=null) {
50             System.out.println(current.data+" ");
51             current=current.next;
52         }
53         System.out.println("");
54     }
55     
56     
57     
58 }

双向链表：

概念：

我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。

双向链表的实现：

  1 import org.junit.jupiter.api.Test;
  2 
  3 /**
  4  *  双向链表的实现
  5  * @author wydream
  6  *
  7  */
  8 
  9 public class TwoWayLinkedList {
 10     
 11     private Node head;//链表头
 12     private Node tail;//链表尾
 13     private int size;//链表长度
 14     
 15 
 16     private class Node{
 17         private Object data;
 18         private Node next;
 19         private Node prev;
 20         
 21         public Node(Object obj){
 22             this.data=obj;
 23         }
 24         
 25     }
 26     
 27     public TwoWayLinkedList(){
 28         size=0;
 29         head=null;
 30         tail=null;
 31     }
 32     
 33     //在表头添加新节点
 34     public void addHead(Object obj) {
 35         Node node=new Node(obj);
 36         //如果链表长度为零，则添加的这个元素就是头节点和尾节点
 37         if(size==0) {
 38             head=node;
 39             tail=node;
 40         }else {
 41             head.prev=node;
 42             node.next=head;
 43             head=node;
 44         }
 45         
 46         size++;
 47     }
 48     
 49     //在链表尾添加新节点
 50     public void addEnd(Object obj) {
 51         Node newNode=new Node(obj);
 52         if(size==0) {
 53             head=newNode;
 54             tail=newNode;
 55         }else {
 56             tail.next=newNode;
 57             newNode.prev=tail;
 58             tail=newNode;
 59         }
 60         size++;
 61     }
 62     
 63     //删除链表头
 64     public Node deleteHead() {
 65         Node temp=head;
 66         if(size!=0) {
 67             head=head.next;
 68             head.prev=null;
 69             size--;
 70         }
 71         return temp;
 72     }
 73     
 74     
 75     //删除链表尾
 76     public void deleteEnd() {
 77         Node end=tail;
 78         if(size!=0) {
 79             tail=tail.prev;
 80             tail.next=null;
 81             size--;
 82         }
 83     }
 84     
 85     
 86     //获取链表节点个数
 87     public int getLength() {
 88         return size;
 89     }
 90     
 91     //判断链表是否为空
 92     public boolean isEmpty() {
 93         if(size>0) {
 94             return true;
 95         }
 96         return false;
 97     }
 98     
 99     //显示节点信息
100     public void display() {
101         if(size>0) {
102             Node node=head;
103             int tempSize=size;
104             if(tempSize==1) {
105                 System.out.println("["+node.data+"]");
106                 return;
107             }
108             while(tempSize>0) {
109                 if(node.equals(head)) {
110                     System.out.print("["+node.data+"->");
111                 }else if(node.equals(tail)) {
112                     System.out.print(node.data+"]");
113                 }else {
114                     System.out.print(node.data+"->");
115                 }
116                 node=node.next;
117                 tempSize--;
118             }
119             System.out.println();
120         }else {
121             System.out.println("[]");
122         }
123         
124     }
125     
126     @Test
127     public void test() {
128         TwoWayLinkedList tl=new TwoWayLinkedList();
129         tl.addEnd("1");
130         tl.addEnd("2");
131         tl.addEnd("3");
132         tl.addEnd("4");
133         tl.deleteHead();
134         tl.deleteEnd();
135         tl.display();
136     }
137     
138     
139 }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-07-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

存储

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

存储

登录后参与评论

0 条评论

热度

数据结构——线性表之链式存储结构

数据结构——线性表之链式存储结构

单链表：

概念：

单链表的操作：

有序链表：

概念：

有序链表的实现：

双向链表：

概念：

双向链表的实现：

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐